畜栏预定

AcWing-111-畜栏预定

分析

见《进阶指南》第43页。

实现

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

const int N = 50010;
struct Cow {
    int l, r;
    int idx, corral_idx;
};
struct Corral {
    int idx;
    int r;
    bool operator < (const Corral& o) const {
        return r > o.r;
    }
};
Cow cow[N];
priority_queue<Corral> pq;

bool cmp1 (const Cow& a, const Cow& b) {
    if (a.l == b.l)
        return a.r < b.r;
    return a.l < b.l;
}
bool cmp2 (const Cow& a, const Cow& b) {
    return a.idx < b.idx;
}

int main () {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i) {
        scanf("%d%d", &cow[i].l, &cow[i].r);
        cow[i].idx = i;
    }

    sort(cow + 1, cow + n + 1, cmp1);
    int cnt = 0;
    for (int i = 1; i <= n; ++ i) {
        if (pq.empty() || pq.top().r >= cow[i].l) {
            cow[i].corral_idx = ++ cnt;
            pq.push({ cnt, cow[i].r });
        } else {
            Corral temp = pq.top();
            pq.pop();
            pq.push({ temp.idx, cow[i].r });
            cow[i].corral_idx = temp.idx;
        }
    }
    sort(cow + 1, cow + n + 1, cmp2);
    
    printf("%d\n", cnt);
    for (int i = 1; i <= n; ++ i) printf("%d\n", cow[i].corral_idx);
    return 0;
}