[백준 11000] 알고리즘 110일차 : 강의실 배정

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

11000번: 강의실 배정

 

C++ 그리디 알고리즘, 우선순위 큐

강의 시간표 (시작시간, 종료시간)이 주어지고 최소한의 강의실을 배정하여 강의실 개수를 출력하는 문제

 

접근방법

그리디 문제 중에 이런 문제는 처음 봐서 좀 헤맸다. 처음엔 브루트포스인가 싶어서 이중포문으로 돌렸었는데

역시 시간복잡도 때문에 아니었던 것 같다.

 

우선순위큐 두개를 사용해서 풀이한다.

하나는 모든 강의 시간표가 시작시간의 오름차순으로 정렬되어있다(시작시간이 같을 경우 종료시간 오름차순) : pq

다른 하나는 필요한 강의실을 담고있는데, 종료시간이 이른 순으로 (오름차순) 정렬되어있는 큐이다. : cq

 

pq에서 하나씩 빼서 cq의 top(배정된 강의실 중 가장 빨리 끝나는 강의실의 종료시간)과 비교한다.

그 강의실에서 수업할 수 있으면(cq.top() <= pq.top().시작시간) 이면

그 강의실에 배정한다. 즉 그 강의실의 종료시간이 갱신된다.

 

cq는 종료시간 순으로 정렬되는 우선순위큐이기 때문에

cq의 top에는 다시 종료시간이 제일 이른 강의실이 top에 위치한다.

 

이를 pq에 있던 모든 강의가 배정될 때까지 반복한다.

 

그리고 cq의 size(배정된 강의실 수)를 출력하면 끝

 

소스코드

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

struct comp{
    bool operator()(pair<int,int> a, pair<int, int> b){
        if(a.first == b.first){
            return a.second > b.second;
        }else{
            return a.first > b.first;
        }
    }
};

int main(){
    //init & input
    int N;
    cin >> N;
    
    priority_queue<pair<int, int>, vector<pair<int, int>>, comp> pq;
    priority_queue<int, vector<int>, greater<>> cq;

    int a,b;
    for(int i = 0 ; i < N ; i++){
        cin >> a >> b;
        pq.push(make_pair(a, b));
    }
    
    //process
    cq.push(pq.top().second);
    pq.pop();
    
    while(!pq.empty()){
        if(pq.top().first >= cq.top()){
            cq.pop();
            cq.push(pq.top().second);
            pq.pop();
        }else{
            cq.push(pq.top().second);
            pq.pop();
        }
    }
    
    //output
    cout << cq.size() << "\n";
    
    return 0;
}