백준 11000 강의실 배정

 

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

11000번: 강의실 배정

 

 

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


using namespace std;


vector<pair<int, int>> cls;

priority_queue<int, vector<int>, greater<int>> pq;






int main() {


    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;


    cin >> n;

    for (int i = 0; i < n; i++) {
        int s, e;

        cin >> s >> e;

        cls.push_back({s, e});

    }

    //먼저 시작하는 회의부터 계산
    sort(cls.begin(), cls.end());


    pq.push(cls[0].second);
    for (int i = 1; i < n; i++) {
        //현재 확인하려는 수업이 가장 빨리 끝나는 수업보다 늦게 시작한다면 해당 강의실의 수업 갱신
        if (cls[i].first >= pq.top()) {
            pq.pop();
            pq.push(cls[i].second);
        }
        //아니면 새로운 강의실에서 수업 진행
        else {
            pq.push(cls[i].second);
        }


    }


    cout << pq.size();




    return 0;
}

 

예시 1번 케이스를 예로 들어보자

3

1 3

2 4

3 5

 

pq는 각 강의실의 마지막 시간, 즉 해당 강의실을 사용할 수 있는 시작 시간이다.

우선순위 큐를 사용하게 되면 가장 빨리 사용할 수 있는 강의실에 강의를 배정할 수 있게 된다.

 

일단 첫 번째 강의는 1번 강의실을 배정받는다.

그 다음 강의는 1번 강의와 일정이 겹치므로 다음 강의실을 배정받는다.

마지막 강의는 가장 빨리 끝나는 1번 강의보다 늦게 시작하므로 이 강의실을 사용할 수 있는 시각을 3->5로 업데이트 한다.