有N头牛在畜栏中吃草。

每个畜栏在同一时间段只能提供给一头牛吃草，所以可能会需要多个畜栏。

给定N头牛和每头牛开始吃草的时间A以及结束吃草的时间B，每头牛在[A,B]这一时间段内都会一直吃草。

当两头牛的吃草区间存在交集时（包括端点），这两头牛不能被安排在同一个畜栏吃草。

求需要的最小畜栏数目和每头牛对应的畜栏方案。

输入格式

第1行：输入一个整数N。

第2..N+1行：第i+1行输入第i头牛的开始吃草时间A以及结束吃草时间B，数之间用空格隔开。

输出格式

第1行：输入一个整数，代表所需最小畜栏数。

第2..N+1行：第i+1行输入第i头牛被安排到的畜栏编号，编号从1开始，只要方案合法即可。

数据范围

1≤N≤500001≤N≤50000,

1≤A,B≤10000001≤A,B≤1000000

输入样例：

51 102 43 65 84 7

输出样例：

412324

 

算法：贪心 + 小根堆

题解：建立一个小根堆，把结束时间最早的畜栏放再堆顶，然后判断下一头牛的开始时间是否比堆顶的那个结束时间小，如果小的话，就可以接着用那个畜栏，否则新建一个畜栏。

 

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int maxn = 5e5+7;struct node {    int start, end, id;    friend bool operator <(node a, node b) {    //重载运算符        if(a.end == b.end) {            return a.start > b.start;        }        return a.end > b.end;    };}arr[maxn];priority_queue
         
           q;       //建立最小堆bool cmp(node a, node b) {    if(a.start == b.start) {        return a.end < b.end;    }    return a.start < b.start;}int main() {    int n;    scanf("%d", &n);    for(int i = 1; i <= n; i++) {        scanf("%d %d", &arr[i].start, &arr[i].end);        arr[i].id = i;    }    sort(arr + 1, arr + n + 1, cmp);    int cnt = 0;    int ans[maxn];    for(int i = 1; i <= n; i++) {        if(!q.empty() && q.top().end < arr[i].start) {            ans[arr[i].id] = ans[q.top().id];   //使用前面那个畜栏            q.pop();        } else {            cnt++;            ans[arr[i].id] = cnt;      //使用新的畜栏        }        q.push(arr[i]);    }    cout << cnt << endl;    for(int i = 1; i <= n; i++) {        cout << ans[i] << endl;    }    return 0; }