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

문제 링크 : 백준 11000번

[문제 접근]

정렬과 우선순위 큐를 이용해 풀었다.

1. s를 기준으로 오름차순으로 정렬해준다.
2. 우선순위 큐를 오름차순으로 설정해주고 첫 강의가 끝나는 시간을 넣어준다.(우선순위 큐가 강의실이라고 생각하면 된다.)
3. 나머지 강의를 돌면서 조건에 따라 우선순위 큐를 컨트롤한다.
   • 모든 강의실 중에 가장 빨리 끝나는 강의실을 선택한다. (q.top())
   • 해당 강의실이 끝나기전에 현재 강의가 시작되면 (now>s) 강의실을 하나 늘려준다. (q.push(t))
   • 해당 강의실이 끝난 후에 강의가 시작되면 (now<=s) 강의실을 늘릴 필요 없이 그 강의실에서 강의를 시작한다. (q.pop(), q.push(t))
4. 최종적으로 남아있는 강의실의 개수가 정답이다. (q.size())

⭐ 빈 강의실에는 앞으로 진행할 강의를 넣으므로 절대 강의실이 비어있을 일은 없다.

[소스 코드]

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

using namespace std;
int n;

struct node {
    int s,t;
};

node arr[200001];

bool cmp(node a, node b) {
    if(a.s==b.s) {
        return a.t<b.t;
    }
    return a.s<b.s;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for(int i=0 ; i<n ; i++) {
        cin >> arr[i].s >> arr[i].t;
    }
    sort(arr, arr+n, cmp);

    priority_queue<int, vector<int>, greater<int>> q;
    q.push(arr[0].t);
    for(int i=1 ; i<n ; i++) {
        int s = arr[i].s, t = arr[i].t;
        int now = q.top();
        if(now>s) {
            q.push(t);
        } else {
            q.pop();
            q.push(t);
        }
    }
    cout << q.size();
    return 0;
}