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

문제

11000번: 강의실 배정

풀이

그리디, 우선순위 큐

 

[백준][C++] 2170: 선 긋기

위의 문제가 생각나는 문제이다. A강의와 B강의가 서로 같은 강의실을 사용하려면 A강의가 B강의의 시작하는 시간보다 빨리 끝나야 한다. 

 

오름차순 우선순위 큐를 만든다. 

priority_queue<int, vector<int>, greater<int>> pq;

강의를 빨리 시작하면서 빨리 끝나는 순서로 정렬한다.

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

가장 빨리 시작하는 강의인 A가 우선순위 큐에 들어가는데, 앞선 강의에서 필요한 것은 종료 시간이므로 종료 시간을 우선순위 큐에 넣는다. 

다음으로 빨리 시작하는 강의는 B강의이다. B강의의 시작 시간은 2이다. 현재 우선순위 큐의 top에는 A의 종료 시간인 3이 들어 있다. A의 종료 시간이 B의 시작 시간보다 늦으므로, 두 강의는 같은 강의실에서 진행할 수 없다.

이제 B강의의 종료 시간인 4도 우선순위 큐에 넣는다. 우선순위 큐의 size는 사용하는 강의실의 수이다. 현재 강의실은 2개를 사용하고 있다. 

이제 C강의를 보자. 현재 우선순위 큐의 top에는 A의 종료 시간인 3이 들어 있다. 이번에는 A의 종료 시간과 C의 시작 시간이 서로 같으므로 두 강의는 서로 같은 강의실에서 진행할 수 있다. 이제 A의 강의는 종료되었으므로, 우선순위 큐에서 제거하고, C강의의 종료 시간을 우선순위 큐에 넣는다. 

for (int i = 1; i < N; ++i)
{
    int current = pq.top();

    // 가장 빨리 끝나는 수업이 i번째 수업의 시작시간보다 빨리 끝나는 경우
    // i번째 수업과 같은 강의실에서 진행할 수 있다. 
    // 늦게 끝나는 경우 다른 강의실에서 진행해야 한다. 
    if (current <= lecture[i].first)
    {
        pq.pop();
        pq.push(lecture[i].second);
    }
    else
    {
        pq.push(lecture[i].second);
    }

    // pq의 size는 현재 사용하는 강의실의 수이다.
    answer = max(answer, (int)pq.size());
}

이를 진행하면서 우선순위 큐의 size의 최댓값을 구한다. 

코드

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

using namespace std;

vector<pair<int, int>> lecture;
priority_queue<int, vector<int>, greater<int>> pq;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin >> N;

    for (int i = 0; i < N; ++i)
    {
        int S, T;
        cin >> S >> T;
        lecture.push_back(make_pair(S, T));
    }

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

    pq.push(lecture[0].second);
    int answer = 1;

    for (int i = 1; i < N; ++i)
    {
        int current = pq.top();

        // 가장 빨리 끝나는 수업이 i번째 수업의 시작시간보다 빨리 끝나는 경우
        // i번째 수업과 같은 강의실에서 진행할 수 있다. 
        // 늦게 끝나는 경우 다른 강의실에서 진행해야 한다. 
        if (current <= lecture[i].first)
        {
            pq.pop();
            pq.push(lecture[i].second);
        }
        else
        {
            pq.push(lecture[i].second);
        }

        // pq의 size는 현재 사용하는 강의실의 수이다.
        answer = max(answer, (int)pq.size());
    }

    cout << answer;

    return 0;
}