[백준] 11000. 강의실 배정

이 문제의 핵심은 최소의 강의실로 모든 강의를 처리해야한다는 것.
처음에는 다음의 알고리즘을 생각했다.

[주어진 것]
강의실 배열 : 배열의 요소 하나는 강의실 하나를 의미하며, 들어있는 값은 강의실이 끝나는 시간을 의미함.
강의 배열 : 입력으로 주어지는 강의의 배열

1. 입력받은 강의들을 강의가 끝나는 순서대로 정렬한다.
2. 맨 처음 강의실 배열에는 아무것도 없을테니, 0번째 강의의 끝나는 시간을 넣어놓는다.
3. 1번 강의부터 차례대로 다음 규칙에 맞춰 강의실 배열을 모두 돈다.
3-1. 강의실 배열 요소의 값들 중, 주어진 강의의 시작시간보다 작거나 같은 것이 있다면, 주어진 강의의 끝나는 시간으로 바꾼다.
3-2. 강의실 배열의 요소들을 전부 돌았으나, 3-1을 만족시키는 강의실이 없다면, 강의실 배열에 주어진 강의의 끝나는 시간을 값으로 가지는 요소를 추가한다.
4. 강의실 배열은 매번 정렬한다.
5. 모두 끝났을 때, 강의실 배열의 크기가 강의실을 최소로 사용하는 값과 같다.

이럴 경우 시간복잡도는 O(N²logN)이다.
하지만, 주어진 N의 크기가 200,000이므로 이는 제한시간을 초과한다.

따라서 뭔가 말도 안 되게 간단한 방법이 있다는 것을 암시한다.
대부분 이런 느낌이 들면, 그리디 알고리즘을 설계해야한다.

일단 매번 강의실 배열을 정렬해야하는 부분을 해결하고자 했다.
배열의 첫 번째 요소가 항상 모든 강의실 중 가장 먼저 끝나는 강의실이라면 좋겠다고 생각했다.
이는 우선순위 큐가 필요하다. 우선순위큐는 push()와 pop() 한 번에 O(logN)이기 때문이다.
만약 이를 통해 알고리즘을 설계하면 시간복잡도는 O(NlogN)으로 이는 200,000 * 17.6.. ≒ 3,600,000 정도로 굉장히 빠른 속도라 할 수 있다.

큐의 맨 위에는 가장 먼저 끝나는 강의실이 주어진다. 이에 끝나는 시간이 빠른 순서대로 정렬된 강의를 차례대로 다음 규칙에 맞게 큐에 넣는다.
1. top()보다 주어진 강의의 시작시간이 크거나 같다면, 큐에서 pop()한 후, 주어진 강의의 끝나는 시간을 push()한다.
2. 1번을 만족하지 못한다면, 주어진 강의의 끝나는 시간을 push()한다.

완벽해보였지만 틀렸따.. 이유는 강의의 정렬방식 때문이었다.

이 문제의 핵심은 최소의 강의실로 모든 강의를 처리해야 한다고 서두에 언급했다.
다음 두가지가 잘 맞물리지 않았기 때문에 틀린것이었다.
1. 우선순위 큐에서는 가장 먼저 끝나는 강의실부터 주어진다.
2. 위 강의실과 비교하는 강의들은 끝나는 시간이 빠른 순서대로 정렬되어있다.

우선순위 큐를 사용하기 때문에, 다음 경우를 처리하지 못한다.
주어진 입력값이 다음과 같다고 해보자.
4
1 2
1 3
3 4
2 5
처음 제출한 코드가 틀린 이유는 다음 상황에서 효율적인 강의 배치가 불가능하기 때문이다.
큐에 다음과 같이 있을 때, [2, 3]
top()으로 볼 수 있는 값은 2이다. 강의는 끝나는 시간을 기준으로 정렬되었기 때문에 주어지는 강의는 (3, 4)이고 이 강의는 큐에 들어간 강의중 3으로 끝나는 강의실에 배치되어야 하나, 우선순위 큐의 성질때문에 2가 먼저 나오게 된다.
따라서 2개의 강의실만 사용하면 되는 위 입력은 정렬방식이 틀려서 3개의 강의실을 사용해버린다.

[올바른 코드]

#include <iostream> 
#include <queue> 
#include <algorithm> 
#include <utility> 
using namespace std; 

typedef pair<int, int> pii; 

const int MAX_N = 2e5; 
pii lec[MAX_N]; 
priority_queue<int> pq; 
int N; 

int main(){
    ios::sync_with_stdio(0); 
    cin.tie(0); cin >> N;
    
    for(int i=0; i<N; i++) cin >> lec[i].first >> lec[i].second; 
    sort(lec, lec+N); 
    pq.push(-lec[0].second);
    
    for(int i=1; i<N; i++) { 
    	int p = pq.top(); 
        if(-p <= lec[i].first) pq.pop(); 
        pq.push(-lec[i].second); 
    } 
    
    cout << pq.size() << "\n"; 
}

[왜 그랬을까?]
난 왜 강의실을 끝나는 시간이 빠른 순서대로 정렬했는가 하면, 그동안 풀었던 강의 스케줄링 문제들이 강의가 끝나는 순서대로 배치했을 때 최대한 많은 강의를 들을 수 있었기 때문이다. 하지만 이 문제는 설명만 비슷하고 풀어내는 방식이 아예 달랐다. 그냥 생각을 덜한 부분..