这道题，是学长给我们布置的学习用的题目，重在给我们讲解了什么是优先队列以及其对应的贪心问题。
好了，先送上（中文翻译过的题意）手动「滑稽」
Oh those picky N (1 <= N <= 50,000) cows! They are so picky that each one will only be milked over some precise time interval A..B (1 <= A <= B <= 1,000,000), which includes both times A and B. Obviously, FJ must create a reservation system to determine which stall each cow can be assigned for her milking time. Of course, no cow will share such a private moment with other cows.
Help FJ by determining:
- The minimum number of stalls required in the barn so that each cow can have her private milking period
- An assignment of cows to these stalls over time
Many answers are correct for each test dataset; a program will grade your answer.
Input
Line 1: A single integer, N
Lines 2..N+1: Line i+1 describes cow i's milking interval with two space-separated integers.
Output
Line 1: The minimum number of stalls the barn must have.
Lines 2..N+1: Line i+1 describes the stall to which cow i will be assigned for her milking period.
Sample Input
5
1 10
2 4
3 6
5 8
4 7
Sample Output
4
1
2
3
2
4
Hint
Explanation of the sample:
Here's a graphical schedule for this output:
Time 1 2 3 4 5 6 7 8 9 10
Stall 1 c1>>>>>>>>>>>>>>>>>>>>>>>>>>>
Stall 2 .. c2>>>>>> c4>>>>>>>>> .. ..
Stall 3 .. .. c3>>>>>>>>> .. .. .. ..
Stall 4 .. .. .. c5>>>>>>>>> .. .. ..
Other outputs using the same number of stalls are possible.
哦那些挑剔的N（1 <= N <= 50,000）牛！它们非常挑剔，只能在精确的时间间隔A..B（1 <= A <= B <= 1,000,000）内进行挤奶，包括时间A和B.显然，FJ必须创建预订系统确定每头牛可以分配哪个牛奶挤奶时间。当然，没有牛会与其他牛分享这样一个私人时刻。
通过确定：帮助FJ
- 谷仓所需的最小摊位数量，以便每头奶牛可以有自己的挤奶期
- 随着时间的推移，牛将这些摊位分配给这些摊位
许多答案对于每个测试数据集都是正确的; 一个程序将评分你的答案。
输入
第1行：单个整数，N
第2..N + 1行：第i + 1行用两个空格分隔的整数描述奶牛的挤奶间隔。
产量
1号线：谷仓必须有的最小摊位数量。
第2..N + 1行：第i + 1行描述了奶牛我将被分配给她的挤奶期的摊位。
示例输入
5
1 10
2 4
3 6
5 8
4 7
示例输出
4
1
2
3
2
4
暗示
示例说明：
以下是此输出的图形计划：
时间1 2 3 4 5 6 7 8 9 10
档位1 c1 >>>>>>>>>>>>>>>>>>>>>>>>>>>
档位2 .. c2 >>>> >> c4 >>>>>>>>> .. ..
摊位3 .. .. c3 >>>>>>>>> .. .. ..
摊位4 .. .. .. c5> >>>>>>>> .. ..
其他使用相同数量档位的输出也是可能的。
接下来我得讲讲我的思路（对大佬而言可能过于繁琐，但是适用于广大萌新哦），这是我第一次遇上这类题，把它记下来写在小本本上去。
这道题的目的是让我们用尽量少的摊位，且让所有在同一摊位的“区间段”互不干涉（碰头也不行）。
那么，这里所需要用到的算法就是priority_queue以及总所周知的贪心，在这里，我们要活用优先队列，优先队列有冗长的“priority_queue<int ,vector<int> ,less<int> >”以及“priority_queue<int ,vector<int> ,greater<int> >”，但是，我们不用那么复杂的处理，在用struct定义一个结构体类型时，我们用了些窍门：
friend bool operator<(node a, node b)
{
return a.en>b.en;
}
使得将来的优先队列中的所有元素都是后结束的在前，但是，这又是远远不够的，我们知道了结束，还需要有开始的排序，那么，sort()操作就少不了，此处插入一条结构体类型的快排：
bool cmp (node a, node b)
{
return a.st<b.st;
}
现在，我们搞定了对全体区域的排序，接下来就要讲到贪心操作了，我们为了使得尽可能少的用摊位，就需要使得每个摊位尽可能的充实，首先，第一头牛无论如何都是需要一个摊位的，把它放入优先队列，我们将它给放入第一个摊位，再将后来的牛一一进入，从第二头牛开始直至第N头牛，我们在判断他的左端区间是否可以紧跟上一头牛的右端区间，如果可以，把它放入上一头牛的摊位上去，则将这头牛入队列之前，前一头牛已经无法作为比较对象了，那么T了他！如果这头牛太矫情，他没法跟上一头牛保持良好距离，那么，它的摊位就是上一头牛的摊位+1，因为上一头牛后面还没找到可以尾随的对象，不能T了，所以只需要把这头牛入队就行。
到了附上AC代码的时候了：（写的菜，请多多包容）
#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
int N;
int place[50005];
struct node
{
int st,en,pos;
friend bool operator<(node a,node b)
{
return a.en>b.en;
}
}a[50005];
bool cmp(node a,node b)
{
return a.st<b.st;
}
priority_queue<node> Q;
int main()
{
while(scanf("%d%*c",&N)!=EOF)
{
int ans=1;
for(int i=1;i<=N;i++)
{
scanf("%d %d%*c",&a[i].st,&a[i].en);
a[i].pos=i;
}
sort(a+1, a+N+1, cmp);
place[a[1].pos]=1;
Q.push(a[1]);
for(int i=2;i<=N;i++)
{
if(!Q.empty()&&Q.top().en<a[i].st)
{
place[a[i].pos]=place[Q.top().pos];
Q.pop();
}
else
{
ans++;
place[a[i].pos]=ans;
}
Q.push(a[i]);
}
printf("%d\n",ans);
for(int i=1;i<=N;i++)
{
printf("%d\n",place[i]);
}
while(!Q.empty())
{
Q.pop();
}
}
return 0;
}
Thanks for watching!
希望对大家有帮助吧，下方可以留言我哪里有可以优化的地方，谢谢大佬们了！
