04. 그리디 문제 [BOJ 11000번]

1. 관련 문제 🎯

문제 : 백준 11000 강의실 배정 👩‍🏫
난이도 : 골드 5

2. 문제 속 정보 🧩

1️⃣ Si(= 수업 시작시간)에 시작해서 Ti(= 수업 종료시간)에 끝나는 N개의 수업이 주어진다.
2️⃣ 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다.
3️⃣ 수업이 끝난 직후에 다음 수업을 시작할 수 있다.
(Ti <= Sj일 경우, i 수업과 j 수업은 같이 들을 수 있다.)

• 문제 예시를 통해서, 살펴보자!
  (S,T) = (1,3), (2,4), (3,5)가 주어진다.
  아래의 그림을 통해서, (1,3)과 (3,5)가 같은 강의실을 사용하고, (3,5)가 다른 강의실을 사용하여 총 2개의 강의실을 사용해야 한다는 것을 알 수 있다.
  

3. 문제 접근 방법 📒

• 처음에 이 문제를 풀기 시작했을 때에는 그리디 문제의 대표 문제인 거스름돈 문제에서 큰 돈부터 부여하는 것처럼 수업 시간이 긴 것부터 강의실을 배정하려고 했다. 그러나, 계속해서 '틀렸습니다😡'라는 결과가 나왔다!!
• 그래서, 탐욕 알고리즘을 찾아보다가 "최적의 해를 구하기 위해서는 첫 번째 활동이 최대한 일찍 끝나면 된다. 그래야 다른 활동들을 더 많이 선택할 수 있기 때문이죠"라는 참고자료 1을 보고 이를 적용하기로 하였다.
• 아래의 예시는 한 강의실에서 여러 개의 수업을 하려고 할 때 한 번에 가장 많은 수업을 할 수 있는 경우이다. 그러나, 우리는 최소의 강의실을 찾아내는 것이기 때문에 거의 비슷한 문제라고 할 수 있다.
• 아래의 사진처럼, 강의의 시간들이 배정되어 있는 경우에는 첫 선택으로 가장 빨리 끝나는 A1을 고른다. A1을 고르면 해당 강의실에서는 A1이랑 겹치는 A2와 A4를 고를 수 없다. 그 다음 선택은 다음으로 일찍 끝나는 A3가 된다. 그 다음은 A6, 마지막은 A8이 되어 최종적으로 해당 강의실이 선택하는 강의시간은 {A1, A3, A6, A8}이 된다.
  
• 사진 출처 : https://www.zerocho.com/category/Algorithm/post/584ba5c9580277001862f188

참고 자료 1 : 탐욕 알고리즘
참고 자료 2 : 백준 1100번 "강의실 배정" 풀이

4. 문제 풀이 🖌️

이 문제의 핵심은 '첫번째 강의가 최대한 일찍 끝나야 한다."는 점이다.
따라서, 이를 위해서 각각의 강의 종료시간을 작은 순서대로 정렬해주며, 가장 먼저 일찍 끝나는 첫번째 강의를 pop할 수 있는 priority_queue를 사용해야 한다.

1. 강의 시작 시간과 종료시간을 입력받는다.

while(N--){
        cin>>S>>T;
        timeTable.push_back({S,T});
    }

2. 강의 시작 시간이 작은 순서대로 정렬한다.

sort(timeTable.begin(), timeTable.end());

3. 강의 종료시간을 priority_queue에 넣어준다.

priority_queue<int, vector<int>, greater<int>> pq;
    
pq.push(timeTable[0].second);	//강의 종료시간을 넣는다.

for(int i=1; i<timeTable.size(); i++){
    pq.push(timeTable[i].second);
    ...
}

4. priority queue의 top(가장 일찍 끝나는 강의의 종료시간)보다 해당 강의 시작 시간이 크거나 같다면, 해당 강의실에서 강의를 할 수 있으므로 pq.pop()을 하여 해당 강의실에 종료시간을 업데이트한다!

if(pq.top()<=timeTable[i].first){
            pq.pop();
}

• 이때, 앞서서 강의 시작시간이 작은 순서대로 정렬하였기 때문에 해당 강의실의 시간에 중간에 끼어들 수 없으므로 해당 강의실에 종료시간만 업데이트하면 되며 top의 시작시간은 필요없다.

5. 전체 코드 🔑

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

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);

    int N = 0;
    int S =0, T = 0;    //시작시간, 종료시간
    vector<pair<int,int>> timeTable;
    cin>>N;

    while(N--){
        cin>>S>>T;
        timeTable.push_back({S,T});
    }

    //시작시간 순서대로 정렬한다.
    sort(timeTable.begin(), timeTable.end());

    priority_queue<int, vector<int>, greater<int>> pq;
    
    pq.push(timeTable[0].second);

    for(int i=1; i<timeTable.size(); i++){
        pq.push(timeTable[i].second);
        if(pq.top()<=timeTable[i].first){
            pq.pop();
        }
    }
    cout<<pq.size()<<"\n";
}

6. 결과 🏆