[백준 11000] 강의실 배정 (C++)

문제 링크: www.acmicpc.net/problem/11000

11000번: 강의실 배정

1. 주의할 점

- 모든 강의에 대한 정보와, 현재 진행중인 강의를 어떻게 정렬할 것인지 잘 계획한다

 

2. 구현

- 모든 강의를 우선순위 PQ에 담는다. PQ의 경우, 시작시간이 빠른순으로 정렬하며, 시작시간이 같은 경우 종료 시간이 빠른 순으로 정렬한다. 종료시간을 1순위로 할 경우, 아래 TC에서 오답을 받게된다

TC #1
6
1 9
2 11
3 11
4 11
12 15
9 17

Answer: 4

- 현재 강의중인 강의실을 PQ2로 설정하고, 끝나는 시간을 기준으로 오름차순 정렬한다

- PQ의 모든 강의에 대해 탐색을 시작하며, 현재 진행하는 강의가 끝나는 시간보다 새로운 강의가 더 늦게 시작한다면 해당 강의실에서 수업하여 강의실을 추가할 필요 없으므로 PQ2에서 1개를 뽑는다. 이후, 새로운 강의가 끝나는 시간을 PQ2에 추가한다

- 이외의 경우에는 바로 PQ2에 새로운 강의의 끝나는 시간을 추가한다

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
struct info{
    int s,e;
};
struct cmp{
    bool operator()(info &a, info &b){
        if(a.s==b.s){
            return a.e > b.e;
        }
        return a.s > b.s;
    }
};
info tmp;
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    priority_queue<info,vector<info>,cmp> pq;        //전체
    priority_queue<int,vector<int>,greater<int>> pq2;       //현재 강의중인 강의실
    int num,e,s,result=1;
    cin>>num;
    for(int i=0;i<num;i++){
        cin>>s>>e;
        tmp.s=s;
        tmp.e=e;
        pq.push(tmp);
    }
    while(!pq.empty()){
        int cs = pq.top().s;
        int ce = pq.top().e;
        pq.pop();
        if(!pq2.empty()){
            int r = pq2.top();
            if(r<=cs) pq2.pop();
        }
        pq2.push(ce);
        int vv = pq2.size();
        result=max(result,vv);
    }
    cout<<result;
    return 0;
}