[백준] 1374 - 강의실

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

1374번: 강의실

 

내가 제일 어려워하는 그리디 문제이다.

강의실을 가장 효율적으로 배정하는 방법은, 시작한 강의의 종료시간 이후에 가장 빨리 시작하는 강의를 배정하면 된다.

그래서 최소 힙에 현재 진행 중인 강의의 종료시간을 넣어주고 이제 시작해야 할 강의와 비교해서 맞바꾼다는 생각으로 구현하면 된다.

 

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

pair<int, int> arr[100001];

int main() {

    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        arr[a] = { b,c };
    }

    sort(arr + 1, arr + n + 1);

    priority_queue<int, vector<int>, greater<int>> q; //하고 있는 강의의 끝나는 시간

    int ans = 0;

    for (int i = 1; i <= n; i++) {

        while (!q.empty() && q.top() <= arr[i].first) {
            q.pop();
        }

        q.push(arr[i].second);
        ans = max(ans, (int)q.size());
    }

    cout << ans;
}