[백준 11000 - C++] 강의실 배정 : 그리디 알고리즘

www.acmicpc.net/problem/11000

11000번: 강의실 배정

문제

수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다. 

김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 

참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)

수강신청 대충한 게 찔리면, 선생님을 도와드리자!

 

입력

첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)

이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109)

 

출력

강의실의 개수를 출력하라.

 

 

풀이

이 문제는 그리디알고리즘에서 유명한 강의실 배정 문제와는 다르다.

평소에 강의실은 끝나는 시간 기준 정렬이지~ 라고 생각하던 나는 뒷통수 맞았다ㅋㅋㅋㅋ

생각해보면 그 문제는 필요한 최소 강의실 수를 구하는게 아니라 하나의 강의실에서 수업할 수 있는 최대의 강의수 였던 것 같다.

이문제에선 강의와 강의 사이의 빈 시간을 최소로 해주어야한다.

 

여기선 2개의 우선순위 큐를 사용한다.

처음에 강의의 시작시간과 종료시간을 입력받을 때는 시작시간을 기준으로 오름차순 정렬을 하기 위해 s_pq에 push한다.

그런 뒤 하나씩 꺼내면서 종료시간을 기준으로 오름차순 정렬하는 f_pq에 push한다.

 

아래의 입력을 예시로 설명하겠다.

6
1 3
2 5
7 8
4 12
9 10
7 11

 

s_pq에는 <1, 3>, <2, 5>, <4, 12>, <7,8>, <7, 11>, <9, 10>이 저장되어있을 것이다.

맨 처음 <1,3>을 pop한 후 이를 f_pq에 push한다.

그런 뒤 s_pq에서 <2,5>를 pop한다.

이때 시작 시간인 2와 f_pq의 top에있는 것의 종료시간을 비교한다. 3 > 2 이므로 <1,3>과 <2,5>는 하나의 강의실을 사용할 수 없다.

따라서 추가로 강의실이 필요하므로 c_cnt를 1증가시키고 f_pq에 <2, 5>를 push한다.

다음으로 <4,12>를 s_pq에서 pop한다. 이때 역시 시작시간인 4와 f_pq의 top에 있는 <1,3>의 종료시간을 비교한다. 3< 4이므로 <4,12>는 <1,3>이 끝난 강의실에서 수업할 수 있다! 그러므로 <1,3>을 f_pq에서 pop하고 <4,12>를 push한다. 여기선 추가 강의실이 필요없으므로 c_cnt는 그대로둔다.

이렇게 쭉 pop하고 push해가면 된다.

 

요약하면 s_pq(시작시간 기준 오름차순 우선순위 큐)에서 하나씩 pop하면서 그 시작시간을 f_pq(종료시간 기준 오름차순 우선순위 큐)의 top의 종료시간과 비교하면서

시작시간이 더 작은 경우엔 강의실 수를 증가시키고 f_pq에 push하고

그렇지 않은 경우엔 강의실 수를 그대로 두고 f_pq에서 pop한 뒤 push해주어야한다.

 

 

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

priority_queue<pair<int, int>> s_pq;    //시작시간 기준 오름차순
priority_queue<pair<int, int>> f_pq;    //종료시간 기준 오름차순

int main(void){
    int n;
    int s, f;
    int c_cnt;
    int sw;
    
    scanf("%d", &n);
    for(int i=0; i<n; i++){
        scanf("%d %d", &s, &f);
        s_pq.push(make_pair(-s, -f));
    }

    c_cnt = 1;
    
    s = -s_pq.top().first;
    f = -s_pq.top().second;
    s_pq.pop();
    f_pq.push(make_pair(-f, -s));
    
    while(!s_pq.empty()){
        s = -s_pq.top().first;
        f = -s_pq.top().second;
        s_pq.pop();
        sw = 0;
        if(s < -f_pq.top().first){
            c_cnt++;
            f_pq.push(make_pair(-f, -s));
        }
        else{
            f_pq.pop();
            f_pq.push(make_pair(-f, -s));
        }
    }
    printf("%d\n", c_cnt);
}