[11000] 강의실 배정

문제 출처 : https://www.acmicpc.net/problem/11000

분류 : 정렬 및 그리디

백준 11000 강의실 배정

NlogN 안에 강의실을 모두 배정하여 보자

---

구현 포인트

1) 정렬을 하여 문제를 단순화 한다.

2) priority queue를 이용하여 빠르게 강의실을 배정하자.

생각보다 문제 풀면서 뻘짓을 많이 해서 남기기로 했다.

어처구니 없게도 처음에 강의 정보를 정렬해 놓고 생각을 너무 복잡하게 하였다...

(각 종료시간을 set으로 저장한 후 iterator를 통해 현재 강의 정보의 시작시간과 비교하여 

가장 차이가 작은 강의실에 해당 강의를 배정하는 그런 방식으로.. 

물론 이 생각은 논리적으로 맞다.

지금 각 강의실의 종료시간이 4, 5, 6이고, 배정하려는 강의의 시작시간이 7이라면 

당연히 종료시간이 6인 강의실에 배정하는게 매우 considerable하다. 

여기까지는 좋았는데.. 망각하고 있었던 것이 강의 시간을 담고 있는 pair vector를 내가 이미 정렬을 했는데

그렇게 되면 종료시간이 4, 5, 6인 상태에서 시작시간이 7인 강의 정보를 보는 순간에는 

앞으로 배정해야 할 강의가 모두 7보다 같거나 큰 시간에 시작한다는 사실이다. 

따라서 그냥 7보다 작은 강의실이 있기만 하면 아무데나 배정해도 별 상관이 없다는 사실이다.

굳이 set을 돌면서 7과의 차이가 가장 작은 6시 종료 강의실을 찾을 필요가 없다는 것이다..

찾는 과정이 아무리 줄여도 log N이고 set을 수정하면 sorting 때문에 NlogN시간이 추가로 들어서..

시간초과가 날 수 밖에 없다.)

생각보다 간단한 문제였는데..! 결론은 그냥 priority queue에 넣고(Mean heap을 이용)

Top을 확인하여 비교한 후 강의실을 추가할 지 배정이 가능한지를 보고 pq에 넣으면 된다.

코드는 아래와 같다.

#include<cstdio>
#include<queue>
#include<algorithm>
#include<vector>
using namespace std;
 
bool comp(const pair<int, int>& a, const pair<int, int>& b) {
    if (a.first == b.first) return a.second > b.second;
    else return a.first > b.first;
}
 
int main() {
    int N;
    vector<pair<int, int> > work;
    priority_queue<int> pq;
    scanf("%d", &N);
    while (N--) {
        int s, e;
        scanf("%d %d", &s, &e);
        work.emplace_back(s, e);
    }
    sort(work.begin(), work.end(), comp); // work가 정렬됨
    pq.push(-work.back().second);
    work.pop_back();
    while (work.size()) {
        auto& p = work.back();
        int top = -pq.top();
        if (top <= p.first) {
            pq.pop();
            pq.push(-p.second);
        }
        else {
            pq.push(-p.second);
        }
        work.pop_back();
    }
    printf("%d\n", (int)pq.size());
    return 0;
}