[BOJ] 1379 강의실 2

문제

1379번: 강의실 2

N개의 강의가 있다. 우리는 모든 강의의 시작하는 시간과 끝나는 시간을 알고 있다. 이때, 우리는 최대한 적은 수의 강의실을 사용하여 모든 강의가 이루어지게 하고 싶다.

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

풀이

코드

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
 
struct info {
    int nm, s, e;
};
 
struct su {
    int nm, st;
};
 
struct com {
    bool operator() (su a, su b) {
        if (a.st == b.st) return a.nm < b.nm;
        return a.st < b.st;
    }
};
 
bool comp(info a, info b) {
    if (a.s == b.s and a.e == b.e) return a.nm < b.nm;
    else if (a.e == b.e) return a.s > b.e;
    return a.e > b.e;
}
 
int n;
info arr[100000];
int ans[100001];
priority_queue<su, vector<su>, com> pq;
 
void go() {
    for(int i = 0; i < n; i++) {
        if (pq.empty() or pq.top().st < arr[i].e) {
            pq.push({int(pq.size())+1, arr[i].s});
            ans[arr[i].nm] = pq.size();
        }else{
            int tmp = pq.top().nm;
            ans[arr[i].nm] = tmp;
            pq.pop();
            pq.push({tmp, arr[i].s});
        }
    }
}
 
int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d %d %d", &arr[i].nm, &arr[i].s, &arr[i].e);
    }
    sort(arr, arr + n, comp);
    go();
    printf("%d\n", pq.size());
    for(int i = 1; i <= n; i++) printf("%d\n", ans[i]);
}