백준 11000번 - 강의실 배정

백준 11000번 - 강의실 배정

https://www.acmicpc.net/problem/11000

11000번: 강의실 배정

이 문제는 우선순위 큐를 사용한 문제이다.

처음 문제를 풀 때 실수했던 점은 입력을 받을 때 정렬되서 들어온다고 생각한 것이였다.

(사실 생각한게 아니고 아무 생각없이 그냥 알고리즘만 생각해서 풀었따ㅎ)

그래서 한번 입력받을 때마다 우선순위 큐의 top과 비교해서 정답을 도출했는데 당연히 틀렸다.

 

고민하다가 생각난 풀이법이 우선순위 큐(Priority queue)를 두 개 사용하는 방법이다!

첫 번째 큐에는 모든 강의들을, 두 번째 큐에는 강의가 끝나는 시간만 저장한다.

먼저 전부 입력을 우선순위 큐에 입력받으면 오름차순으로 알아서 정렬된다.

그 다음 첫 번째 큐에서 하나씩 빼면서 두 번째 큐의 top과 비교한다. 

두 번째 큐에는 끝나는 시간들만 저장되어 있는데, 이는 각 강의실이 끝나는 시간, 즉 몇 시 부터 그 강의실을 사용할 수 있는지가 저장되어 있는 것이다.

또한 우선순위 큐이기 때문에 두 번째 큐의 top만 비교해 줘도 된다.

왜냐하면 top이 가장 빨리 끝나는 시간이므로 그 시간보다 더 빨리 시작해야 하는 강의라면 무조건 새로운 강의실을 편성해야 하기 때문이다.

따라서 첫 번째 큐의 사작 시간과 두 번째 큐의 top을 계속해서 비교해주며 답을 구할 수 있다.

 

#include <iostream>
#include <queue>
#include <vector>
#pragma warning(disable:4996)
using namespace std;
 
int main() {
    int n, a, b;
    int ans = 0;
    scanf("%d", &n);
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
    priority_queue<int, vector<int>, greater<int>>end;
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &a, &b);
        q.push(make_pair(a, b));
    }
    while (!q.empty()) {
        if (end.empty() || q.top().first < end.top()) ans++;
        else end.pop();
        end.push(q.top().second);
        q.pop();
    }
    printf("%d\n", ans);
}

 

코드는 간단하다. 18번째 줄의 end.empty() 조건은 첫 번째 강의를 위한 조건이다.

우선순위 큐를 사용한다면 어렵지 않은 문제였다.