백준 1374 강의실(C++)

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

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

using namespace std;

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

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;

    arr.resize(n);

    for (int i = 0; i < n; i++) {
        int temp;
        cin >> temp >> arr[i].first >> arr[i].second;
    }

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

    pq.push(arr[0].second);
    for (int i = 1; i < n; i++) {
        //현재 확인하려는 수업이 가장 빨리 끝나는 수업보다 늦게 시작한다면 해당 강의실의 수업 갱신
        if (arr[i].first >= pq.top()) {
            pq.pop();
            pq.push(arr[i].second);
        }
        //아니면 새로운 강의실에서 수업 진행
        else {
            pq.push(arr[i].second);
        }


    }


    cout << pq.size();


    return 0;
}

1. 문제

n개의 강의의 번호, 시작 시각, 종료 시각이 주어진다. 한 강의실에는 하나의 강의만 진행되고, 이전 강의가 끝나는 동시에 다음 강의가 시작될 수 있을 때, 필요한 최소 강의실 수를 구하라.

2. 풀이

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

    pq.push(arr[0].second);

전형적인 그리디 문제이다. 강의를 시작 시각 순서로 정렬하고,  우선순위 큐에 각 강의실의 종료 시각을 넣는다.

    for (int i = 1; i < n; i++) {
        //현재 확인하려는 수업이 가장 빨리 끝나는 수업보다 늦게 시작한다면 해당 강의실의 수업 갱신
        if (arr[i].first >= pq.top()) {
            pq.pop();
            pq.push(arr[i].second);
        }
        //아니면 새로운 강의실에서 수업 진행
        else {
            pq.push(arr[i].second);
        }


    }

현재 확인하려는 수업이 가장 빨리 끝나는 수업보다 늦게 시작한다면 그 강의실에서 진행한다. 더 일찍 시작한다면 새로운 강의실이 필요하므로 해당 강의의 종료 시각을 새로 넣어준다. 강의실 당 종료 시각을 우선순위 큐에 넣었으므로 큐의 크기를 출력하면 정답을 구할 수 있다.