题目链接

Stall Reservations POJ - 3190

思路

先根据开始时间排序，后用小根堆维护可选项，没有可选项则向堆中添加。

时间复杂度

$$ O(Nlog(N)) $$

代码

#include <cstdio>
#include <algorithm>
#include <queue>

using namespace std;

const int MAXN = 5e4 + 10;

int a[MAXN], b[MAXN], id[MAXN], ans[MAXN];

bool cmp(int x, int y) {
    return a[x] < a[y];
}

int main() {
    int n;
    scanf("%d", &n);// don't forget &
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &a[i], &b[i]);// don't forget &
        id[i] = i;
    }
    sort(id + 1, id + 1 + n, cmp);
    priority_queue<pair<int, int>, vector<pair<int ,int> >, greater<pair<int, int> > > pque;
    pque.push(make_pair(0, 1));
    for (int i = 1; i <= n; i++) {
        int cur = id[i];
        if (pque.top().first < a[cur]) {
            pair<int, int> nxt = make_pair(b[cur], pque.top().second);
            ans[cur] = nxt.second;
            pque.pop();
            pque.push(nxt);
        } else {
            ans[cur] = (int)pque.size() + 1;
            pque.push(make_pair(b[cur], ans[cur]));
        }
    }
    printf("%d\n", (int)pque.size());
    for (int i = 1; i <= n; i++) {
        printf("%d\n", ans[i]);
    }
    return 0;
}