백준 11000 강의실 배정 (C++)

11000번: 강의실 배정

우선순의 큐를 이용한 문제이다. 먼저 시작과 종료 시간을 벡터로 입력받은 후 정렬을 해준다. 이 후 우선순위 큐를 이용해 반복문을 돌며 그리디 알고리즘을 사용한다. 종료 시간을 우선순위 큐에 넣고 현재 위치의 시작 시간과 우선순위 큐의 top과 비교하여 시간이 겹치지 않는다면 같은 강의실을 사용할 수 있으므로 pop을 이용해 제거해준다. 이를 반복한 후 우선순위 큐의 크기를 출력해준다.
아이디어를 떠올리는데 시간이 걸렸다. 가장 빠른 종료 시간을 우선순위 큐를 이용해 정렬하여 비교한다는 점이 새로운 알고리즘이었다. 이러한 방식을 기억해두자.

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

using namespace std;

int N;
vector<pair<int, int>> v;
priority_queue<int, vector<int>, greater<int>> pq;

void solution() {
    sort(v.begin(), v.end());

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

    for (int i = 1; i < v.size(); i++) {
        pq.push(v[i].second);

        if (v[i].first >= pq.top()) {
            pq.pop();
        }
    }

    cout << pq.size();
}

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

    cin >> N;

    for (int i = 0; i < N; i++) {
        int a, b;
        cin >> a >> b;
        v.push_back({ a,b });
    }

    solution();

    return 0;
}