[백준,c++] 11000번 - 강의실 배정

문제

11000번: 강의실 배정

 

코드

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    
    int n; cin>>n;
    vector<pair<int,int>>v;
    priority_queue<int,vector<int>,greater<int>>pq;
    
    for(int i=0; i<n; i++){
        int start, end; cin>>start>>end;
        v.push_back({start,end});
    }
    sort(v.begin(),v.end());
    
    pq.push(v[0].second);   //젤 첫수업의 끝나는 시간을 먼저 추가
    
    for(int i=1; i<n; i++){
        if(v[i].first>=pq.top()){
            pq.pop();
            pq.push(v[i].second);
        }
        else pq.push(v[i].second);
    }
    cout<<pq.size();
}

 

풀이

문제 이해 자체는 간단한데 어떻게 구현을 해야 할지 계속 고민이 많이 되었습니다. 

1. 수업 시작 시간을 오름차순으로 먼저 정렬한다.
2. 내림차순(최소힙)으로 우선순위 큐를 생성한다.
3. 현재 수업 시작시간 >= 우선순위 큐의 top 도착시간이면 그 강의실에서 계속 들을 수 있다.
   1. 따라서 pq.pop() 을 하여 도착시간을 빼주고
   2. 현재 수업의 도착시간을 다시 pq.push()한다.
4. 현재 수업시간<우선순위 큐의 top 도착시간이면 새로운 강의실을 생성해야 한다.
   1. 따라서 그냥 pop 없이 현재 수업의 도착시간을 pq.push 해준다.

예제 입출력을 기준으로 설명해보겠습니다.

3
1 3
2 4
3 5

 

일단 젤 첫 수업은 무조건적으로 도착시간을 pq에 넣고 그다음 수업부터 계산합니다.

(2,4)를 볼 건데, 현재 수업시작 시간 2가 pq의 3보다 작으므로 강의실이 하나 더 필요하다는 소리가 됩니다. 따라서 pq에 끝나는 시간 4를 추가해줍니다.

(3,5)를 볼건데, 시작 시간 3이 pq 도착시간 3보다 크거나 같으므로 그 강의실에서 연달아서 수업을 들을 수 있습니다. 따라서 끝나는 시간을 갱신해주기 위해 pq.pop() 후 pq.push() 해줍니다.

그리고 모든 수업을 다 돌아보았을 때는 남은 pq의 사이즈가 강의실의 개수가 됩니다.