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

문제

수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다.

김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다.

참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)

수강신청 대충한 게 찔리면, 선생님을 도와드리자!

입력

첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)

이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109)

출력

강의실의 개수를 출력하라.

예제 입출력

• 예제 입력 1

3
1 3
2 4
3 5

• 예제 출력 1

2

Solution

#include <bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N;
    cin >> N;
    vector<pair<int, int>> classes(N);
    for(int i = 0; i < N; i++) cin >> classes[i].first >> classes[i].second;
    sort(classes.begin(), classes.end());

    priority_queue<int, vector<int>, greater<int>> PQ;
    PQ.push(classes[0].second);
    for(int i = 1; i < N; ++i){
        if(PQ.top() <= classes[i].first) PQ.pop();
        PQ.push(classes[i].second);
    }

    cout << PQ.size() << '\n';
}

사실 쉽게 생각하면 그만이지만...이 문제 또한 괜히 어렵게 생각해서 머리가 터질것 같았던 문제였다.
우선 비슷한 문제가 있다. 그리디 알고리즘 대표문제로 회의실 배정이라고 있지 않는가?
https://www.acmicpc.net/problem/1931
아마 많은 사람들이 풀어 봤을 문제고 이 문제도 마찬가지로 풀면 되겠지라고 생각했지만...골드5짜리 문제가 절대 그렇게 대충 풀릴 리가 없지?

실제로 그런식으로 풀었을 때 한번 틀렸다. 차이점이 있다면 우선순위 큐를 사용한 것.

풀이과정을 정리하면 다음과 같다.
1. 우선 정렬을 한다. pair 구조의 vector 니까 first 기준으로 정렬한다.
2. 그후 첫 번째 클래스의 끝나는 시간인 second를 우선순위 큐에 저장한다.
3. vector 내의 데이터를 선형탐색 하며 우선순위 큐의 Top 데이터와 그 다음 클래스의 시작 시간을 비교했을 때 우선순위 큐의 Top 데이터가 작거나 같다면 pop한 뒤 해당 클래스의 second로 교체한다.
4. 만약 그렇지않다면 그냥 바로 해당 클래스의 second를 집어넣는다.

쭉 풀어쓰면 이렇다는거고 간단히 얘기하면 우선순위 큐에는 강의가 끝나는 시간대로 Heap이 구성된다. 강의가 가능 한 놈들로 최대한 구성을 해야 하기 때문에 가장 빨리 끝나는 놈과 비교했을 때 다음 수업이 가능한 녀석이 있다면 바로바로 pop 후 해당 데이터를 집어넣어준다. 이렇게만 보면 과정이 잘 보이지는 않을 것 같다.

3
1 3
2 4
3 5

입력이 이렇게 들어왔다고 생각해보자. 우선순위 큐의 가장 초기상태에는 아마 3이 들어가있을 것이다.

참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)

priority_queue<int, vector<int>, greater<int>> PQ;
PQ.push(classes[0].second);
for(int i = 1; i < N; ++i){
    if(PQ.top() <= classes[i].first) PQ.pop();
    PQ.push(classes[i].second);
}

여기서 if문을 집중해보자. 가장 빨리 끝나는 놈과 그 다음 놈의 시작 시간을 비교했을 때, 시작 시간이 같거나 크다면? 바로 같은 강의실에서 수업을 할 수 있다는 의미다.
즉 바로 강의실에서 수업을 연속해서 한다는 의미해서 해당 top을 pop 해버리고 해당 인덱스의 second값을 push하는 것이다.

골드 문제라 그런지 단순히 지문을 이해하는것도 꽤나 어렵게 느껴진다. 우선순위 큐를 이렇게도 쓸 수 있다는게 참 신기한 문제였다...