1161번: Fair Shuttle

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

참고로 어떤 그룹에서 일부만 버스에 타도 괜찮다.

$O(nc\lg c)$

(s,e,m)이 주어져 있을 때, [s,e] 스케줄이 m개 있다고 생각하자.
그러면 유명한 스케줄링 알고리즘을 응용해서 풀 수 있다.

먼저, 도착지점을 기준으로 오름차순으로 정렬한다.
앞으로 최대 c개의 끝지점의 위치를 가지고 다닐 것이다. 이러한 위치를 a1<a2<...<ac라고 하자.
구간 [s,e]가 보았을 때 ai<=s를 만족하는 최대 ai가 존재할 경우 해당 구간을 스케줄에 집어 넣을 수 있다.
이제 ai를 e로 대체하고 수열을 오름차순으로 유지하며 앞의 행위를 반복한다.

#include<cstdio>
#include<algorithm>
#include<set>
using namespace std;
struct scd {
    int s, e, m;
}sg[50000];
multiset<int> st;
int k, n, c, res;
int main() {
    scanf("%d%d%d", &k, &n, &c);
    for (int i = 0; i < k; i++) scanf("%d%d%d", &sg[i].s, &sg[i].e, &sg[i].m);
    sort(sg, sg + k, [](scd u, scd v) {
        return u.e < v.e;
    });
    for (int i = 0; i < c; i++) st.insert(0);
    for (int i = 0; i < k; i++) {
        auto it = st.lower_bound(-sg[i].s);
        int cnt = 0;
        while (it != st.end() && cnt < sg[i].m) {
            st.erase(it++);
            cnt++;
        }
        res += cnt;
        while (cnt--) st.insert(-sg[i].e);
    }
    printf("%d", res);
    return 0;
}