[백준] 11000 강의실 배정

 

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

11000번: 강의실 배정

각 강의마다 시작하는 시간 s와 끝나는 시간 t 가 주어질 때 최소 필요한 강의실의 수를 구하는 문제 s ~ t 사이에는 다른 강의를 시작할 수 없다. 즉, 어떤 t 보다 작은 s가 존재한다면 반드시 강의실 수를 늘려야 한다. 크거나 같을 때에는 상관 없다. ( [1,2] , [2,3] 이렇게 2개가 있는 경우는 한번에 이어서 한 강의실에서 수업 할 수 있다. ) 즉, 증가가 일어나는 순간은 t 보다 작은 s가 존재할 때 이다. 이것이 성립하는 조건은 반드시 s가 정렬되어 있을 때만 가능하므로 pair<s,t> 에서 s를 기준으로 정렬된 배열을 만들거나 P[s,t] 를 원소로 가지는 우선순위 큐를 만들면 된다. 핵심 아이디어는 N개의 강의가 있는데 이 중 몇 개의 강의가 같은 강의실에서 이루어지는지 확인하는 것 이다. 여기서 말하는 "같은 강의실에서 이루어진다."는 전체 강의 수 N 에서 몇이 감소 되는지 와 같다.

1. 시작 시간을 기준으로 정렬
2. 첫 번째 원소의 끝 시간을 우선순위 큐에 추가
3. 첫 번째 원소 삭제 ( 첫 번째 강의는 반드시 강의실이 필요하다.)
4. 원소의 시작시간이 이때까지 끝 시간의 모음에서 가장 작은 값 보다 크다면
5. 해당 강의는 같은 강의실에서 수업 할 수 있으므로
6. 해당 끝 시간을 가지는 강의는 의미가 없어진다. 왜냐하면 4.의 조건을 만족하는 시작시간이 존재하는 한 최소 시작시간보다 큰 끝시간이 존재하기 때문이다.
7. 그러므로 해당 끝 시간을 pop 한다.
8. 그리고 4.의 조건을 만족하는 시작시간의 끝 시간을 다시 우선순위 큐에 push 한다. 이 우선순위 큐는 이때까지 끝 시간의 모음이다.
9. 다음 원소로 넘어간다.

이런 프로세스로 짜면 된다.

#include <iostream>
#include <algorithm>
#include <queue>
#define P pair<long, long>
using namespace std;
int N;

int main()
{
    cin >> N;
    priority_queue<P> pq;
    priority_queue<int> q;
    for (int i = 0; i < N; i++)
    {
        long a, b;
        cin >> a >> b;
        pq.push(make_pair(-1 * a, -1 * b));
    }
    long start = 0;
    long end = 0;
    q.push(pq.top().second);
    pq.pop();
    while (!pq.empty())
    {
        P t = pq.top();
        start = -1 * t.first;
        end = -1 * t.second;
        if (start >= -1 * q.top()) // 현재 강의의 시작 시간이 현존하는 모든 강의의 끝 시간 보다 크거나 같다면 
            q.pop(); // 이 강의는 같은 강의실에서 이루어질 수 있으므로 그 끝나는 시간을 삭제한다.
        q.push(-1 * end); // 그리고 현재 강의의 끝 시간을 우선순위 큐에 넣는다. 
        pq.pop();
    }
    cout << q.size() << endl;
    return 0;
}