#11000번 강의실 배정 (C++)

문제 링크 : www.acmicpc.net/problem/11000

11000번: 강의실 배정

주의 사항은 다음과 같다.

(1) 테스트 케이스는 200,000개 이며, 강의가 끝날 수 있는 최대 시간값은 10의 9승에 달한다. 

(2) 고로 함부로 2중 for문을 남발하면 시간초과가 발생한다.

 

문제 풀이는 다음과 같다. 

(1) 벡터(int pair)와 우선순위 큐(int)를 구현한다. 이때 강의시간 입력을 벡터에 저장한다.

(2) 벡터는 오름차순으로 정렬해준다. 

(3) 백터의 첫 번째 값의 두번 째 값(=첫번째 강의가 끝나는 시간)을 우선순위 큐에 넣어준다. 

(4) 다음 벡터와 비교했을때 큐에 넣은 값(가장 빨리 끝나는 강의 시간)보다 다음 벡터의 첫 번째 값(=다음 강의의 시작시간)이 크거나 같다면, 큐를 pop해준다. 이 말은 즉, 강의실 1개로 이어서 쓸 수 있음을 뜻한다.

(5) 다음 강의가 끝나는 시간을 큐어 넣어준다.

(6) 최종적으로 큐의 싸이즈를 출력한다.

---

틀렸던 코드

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

int n = 0, c = 0, d = 0;

bool compare(pair<int,int>&a, pair<int,int>&b){
        if(a.first==b.first) return a.second<b.second;
        else return a.first < b.first;
}

int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    vector<pair<int,int>> v;
    queue<int> q;
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> c >> d;
        v.push_back(make_pair(c,d));
    }
    sort(v.begin(), v.end(), compare);
    q.push(v[0].second);
    for(int i=1; i<n; i++){
        if(q.front()<=v[i].first) q.pop();
        q.push(v[i].second);
    }
    cout << q.size() << "\n";
   return 0;
}

테스트 케이스는 통과했지만 결론적으로 틀렸던 코드이다.

우선순위 큐가 아닌 일반 큐로 구현했는데, 우선순위 큐를 통해 매번 값이 들어올때 마다 가장 빨리 끝나는 강의를 맨 앞으로 보내줘야 한다는 점을 간과했다.

---

정답 코드

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

int n = 0, c = 0, d = 0;

int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    vector<pair<int,int>> v;
    priority_queue<int, vector<int>, greater<int>> pq;
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> c >> d;
        v.push_back(make_pair(c,d));
    }
    sort(v.begin(), v.end());
    pq.push(v[0].second);
    for(int i=1; i<n; i++){
        if(pq.top()<=v[i].first) pq.pop(); // 강의실 1개로 나눠쓸수 있는거면 pop
        pq.push(v[i].second);
    }
    cout << pq.size() << "\n";
   return 0;
}