贪心

A：畜栏预定
https://www.acwing.com/problem/content/description/113/

有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≤50000,
1≤A,B≤1000000
输入样例：
1 10
2 4
3 6
5 8
4 7
输出样例：
4
1
2
3
2
4

思路:

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N = 5e4+10;
pair<PII, int> cows[N];//前一个PII存放开始和结束的时间，后一个存放编号
int id[N];
int main()
{
    int n;
    cin>>n;
    for(int i = 0;i < n;i++)
    {
        cin>>cows[i].x.x>>cows[i].x.y;
        cows[i].y = i;
    }
    sort(cows,cows+n);
    priority_queue<PII,vector<PII>,greater<PII>> q;

    for(int i = 0;i < n;i++)
    {
        auto cow = cows[i];
        //q队列存放的是结束时间和组的个数 q.top().x >= cow.x.x代表着当前小顶堆最小的结束时间 比目前取出来的最小的牛的起始时间要大 那么应该新建一个组
        if(q.empty() || q.top().x >= cow.x.x)
        {
            PII stall = {cow.x.y,q.size()+1};
            id[cows[i].y] = stall.y;
            q.push(stall);
        }
        else//否则加入这个组
        {
            auto stall = q.top();
            q.pop();
            stall.first = cows[i].x.y; //改变当前小顶堆最小值的结束时间
            id[cows[i].y] = stall.y;
            q.push(stall);//插入回小顶堆
        }

    }
    cout<<q.size()<<endl;
    for(int i = 0;i < n;i++)
        cout<<id[i]<<endl;
    return 0;
}