(C++) - 백준(BOJ) 11000번 : 강의실 배정 답

www.acmicpc.net/problem/11000

11000번: 강의실 배정

 

풀이방법

 1. 강의 시작시간이 빠른 것이 우선, 만약 강의 시작시간이 같다면 끝나는 시간이 먼저 오도록 정렬해줍니다.

 2. min heap pq(끝나는 시간이 빠른 것이 위로 가도록)를 사용해 강의실을 배정합니다. 우선순위 큐의 원소에는 강의 끝나는 시간이 들어갑니다.

    top()이 강의 시작시간 이하라면 이 강의는 한 강의실에서 이어받으면 되므로 pop 합니다. 이 후 해당 강의의 끝나는 시간을 넣어줍니다.

    

Code

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>; 
int n;
vector<pii> lecture(n);
priority_queue<int, vector<int>, greater<int>> pq;
 
int main(){
    cin >> n;
    lecture.resize(n);

    for(int i = 0; i < n; i++)
        cin >> lecture[i].first >> lecture[i].second;
    sort(lecture.begin(), lecture.end());
    pq.push(lecture[0].second);

    for(int i = 1; i < n; i++){
        if(pq.top() <= lecture[i].first) pq.pop();
        pq.push(lecture[i].second);
    }
    cout << pq.size() << '\n';
}