백준 11000 - 강의실 배정, C++, 우선순위 큐, 그리디

11000번: 강의실 배정

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

using namespace std;

int n, s, t, answer = 1;
// 시작시간, 종료시간
priority_queue<int> classQ;
vector<pair<int, int>> class_time;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // input
    cin >> n;

    for(int i = 0; i < n; i++){
        cin >> s >> t;
        class_time.push_back(make_pair(s, t));
    }

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

    // 강의실 찾기
    /*
    1. 강의실이 다 비어있는 경우
    2. 강의실이 일부만 사용되는 경우 (큐에서 전부 차있는 경우)
    3. 강의실이 전부 찬 경우 
    */
    for(int i = 0; i < n; i++){

        if(classQ.empty()) {
            classQ.push(-class_time[i].second);
        }
        else {
            if(-classQ.top() <= class_time[i].first){
                classQ.pop();
                classQ.push(-class_time[i].second);
            } 
            else {
                answer++;
                classQ.push(-class_time[i].second);
            }
            
        }
    }

    cout << answer << '\n';
}

---

 학교 알고리즘 수업때 배운 작업 스케쥴링 알고리즘이랑 유사한 문제인듯 합니다. 학교에서는 이 방법으로는 항상 최적해를 구할 수 없다고 했으나 다행히도 이 문제는 최적해가 나오는 예제들만 있었나 봅니다.

 

 강의실을 배정하는 조건은 총 3가지입니다.

 

1. 강의실이 전부 비어 있을 때 

2. 강의실이 일부 비어 있을 때 (일부 강의들이 끝난 경우를 의미)

3. 강의실이 전부 차 있을 때

 

 위 3가지를 코드로 표시하면 되는데 1번의 경우 처음 강의실이 들어가는 경우라 단순히 큐에 푸쉬를 해주면 됩니다.

 

 2번의 경우 말 그대로 하기 위해서는 큐에서 강의실을 계속해서 빼주고 a.size() < answer 인지 계속 비교를 해야 하기 때문에 큐속에 강의들의 종료 시각을 두고 이걸 비교하는 방식으로 했습니다. 

 실제 강의라고 생각을 하면 교수님이 다음 강의가 될때까지 강의실을 지키는(?) 모습이 될 겁니다. 이후 새 강의가 들어오면 종료가 되었는지를 체크해 강의실을 빼주고 새 강의를 넣는 것이죠.

 

이렇게 하면 아마 맨 마지막에 answer로 출력하는게 아니라 q.size()를 출력해도 답안이 나올겁니다. 다만 시간적으로 손해가 약간 있으니 굳이 안해도 될 것 같네요