[BOJ - 11000] 강의실 배정(C++)

  문제

 

  접근 방법

수업 시작 시간을 기준으로 정렬 -> 우선순위 큐로 현재 사용 중인 강의실 관리

가장 빨리 끝나는 강의실의 종료 시간 -> 새로운 강의의 시작 시간보다 작거나 같은 경우(pop, push를 통해 재사용)

 

  코드

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

using namespace std;

int N;
vector<pair<int, int>> lesson;

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

    cin >> N;

    lesson.resize(N);

    for (int i = 0; i < N; i++) cin >> lesson[i].first >> lesson[i].second;

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

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

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

    for (int i = 1; i < N; i++) {
        if (pq.top() <= lesson[i].first) {
            pq.pop();
        }
        pq.push(lesson[i].second);
    }

    cout << pq.size();

    return 0;
}

 

  링크

11000번: 강의실 배정