Luogu P2859 [USACO06FEB]摊位预订Stall Reservations

题目链接：​​传送门​​

很明显的要贪心
从左右端点考虑
先排序保证单调性
每次往后看有没有能接上的
单调性才保证了这个往后看的复杂度
于是就很好写了

/**
 * @Date:   2019-03-27T10:41:12+08:00
 * @Last modified time: 2019-03-27T10:41:12+08:00
 */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <algorithm>
#include <climits>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define
#define

using namespace std;
typedef long long ll;
struct node {
    int x, id;
    bool operator < (const node &a) const {
        return x < a.x;
    }
}a[A], b[A];
int ans[A], n, m, k = 1, cnt;

int main(int argc, char const *argv[]) {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i].x >> b[i].x, a[i].id = b[i].id = i;
    sort(a + 1, a + n + 1); sort(b + 1, b + n + 1);
    for (int i = 1; i <= n; i++) {
        if (k <= n) k++;
        if (!ans[b[i].id]) ans[b[i].id] = ++cnt;
        while (a[k].x <= b[i].x and k <= n) k++;
        ans[a[k].id] = ans[b[i].id];
    }
    cout << cnt << endl;
    for (int i = 1; i <= n; i++) cout << ans[i] << endl;
    return 0;
}