BOJ #11000 - 강의실 배정

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

# 문제 분류

그리디 알고리즘

풀이 접근 방법

1. size $N$ = 200000, 1초 제한이므로 $n^2$으로는 절대 풀 수 없다. → 우선순위 큐를 이용, $n\log n$ 풀이
2. 강의를 빨리 시작하는 순서대로 정렬해준다.

a. greater 연산자로 만든 우선순위 큐에 정렬된 첫 강의를 push 하면서 강의가 끝나는 시간의 정보를 기록한다.

b. 우선순위 큐의 top에 있는 정보는 강의실들 중 가장 빨리 끝나는 강의의 시간이므로, top과 비교해준다.

c. top과 비교했을 때, 강의의 시작시간이 같거나 더 늦으면 이미 존재하는 강의실을 사용할 수 있으므로 pop후 push (갱신)

d. top과 비교했을 때, 강의의 시작시간이 더 이르다면 지금 존재하는 강의실 중 어떤 것도 사용할 수 없으므로 push (추가)

3. 이제 강의실을 의미하는 우선순위 큐의 크기만 반환해주면 된다.

회의실배정 문제는 끝나는 시간이 빠른 순으로 정렬하여 단순하게 그리디 알고리즘대로 구현하면 되는 거였지만,
강의실 배정은 그와 반대로 생각해야하고 우선순위 큐를 사용해야한다는 점에서 조금 더 어렵다고 느꼈다.
근데 C++에 내장되어 있는 sort 함수.. 퀵소트라서 최악 $O(n^2)$일텐데 왜 맞은건지는 잘 모르겠다.

코드 설명할건 딱히 없는듯?
20줄에서 첫 강의를 push 해주고 ( 강의실 하나는 무조건 써야할 테니까.. )
그래서 22줄 for문 2부터 돌렸다.

소스 코드

#include <iostream>
#include <algorithm>
#include <utility>
#include <queue>

using namespace std;

pair<int, int> p[200010];
priority_queue<int, vector<int>, greater<int>> pq;
int N, arr[200010], cnt;

int main(){
    cin >> N;
    for(int i=1; i<=N; i++){
        cin >> p[i].first >> p[i].second;
    }

    sort(p+1, p+N+1);

    pq.push(p[1].second);

    for(int i=2; i<=N; i++){
        if(pq.top() <= p[i].first){
            pq.pop();
            pq.push(p[i].second);
        }
        else{
            pq.push(p[i].second);
        }
    }

    cout << pq.size() << endl;

    return 0;
}