UVA 11776

题目链接：https://cn.vjudge.net/problem/UVA-11776

题意：

给出数字n（0<=n<=1000），代表有n个农民，接下来有n行，每行两个数字S和E代表这个农民工作时间为[S,E]；

每个农民工作时，需要有一个enforcer来监督，且每个enforcer一次只能监督一个农民；

求最少需要多少个enforcer.

题解：

这道题我也不太清楚算贪心还是算模拟，可能两者都有一点吧。

首先我们根据正常思维，既然要模拟分配监工去监督农民，那么肯定先给第一个开始做的农民分配一个监工；

所以我们自然而然的想到对农民按工作时间的起点S从小到大排序；

然后，我们也就会进一步自然的想到，如果下一个农民的工作时间和当前农民的工作时间有重合，就要再来一个监工；

但是，经过更加仔细的思考，

由于我们是按农民工作时间的起点S从小到大排，而非按工作终点E排，故可能出现问题：

1 5

2 3

4 10

这种情况，如果单纯地像上面说的那样算，就会算出需要3个监工，而事实上，只需要2个监工就够了。

所以，我们建立一个优先队列，用以存储表示每个监工的监督时间；

并且每个监工有两个变量l和r，表示在当前，监工的工作时间为[l,r]，而优先队列按监督时间的终点从小到大维护。

这样一来，我们就有更加成熟的思路：

①把第一个的农民的工作时间[S,E]当做第一个监工的监督时间[l,r]存入优先队列。

②枚举之后的农民；

③获得队头的值（代表了当前所有监工中，最早空下来的那个），与当前农民进行比较：

　　若当前监工还未空闲，说明所有监工都没空，只能在加一个监工；

　　若当前监工已经空闲，可以监督当前农民，则取出队头，[l,r]修改成当前农民的[S,E]值，再push入优先队列；

④所有农民枚举完毕，ans = 优先队列的size；

AC代码：

 1 #include<cstdio>
 2 #include<queue>
 3 #include<algorithm>
 4 using namespace std;
 5 struct Node{
 6     int l,r;
 7     bool operator<(const Node &oth)const
 8     {
 9         return this->r > oth.r;
10     }
11 }node[1000+5];
12 int n;
13 bool cmp(Node a,Node b){return a.l<b.l;}
14 int main()
15 {
16     int kase=0;
17     while(scanf("%d",&n) && n!=-1)
18     {
19         if(n==0)
20         {
21             printf("Case %d: 0
",++kase);
22             continue;
23         }
24 
25         priority_queue<Node> enforcer;
26         for(int i=0;i<n;i++) scanf("%d%d",&node[i].l,&node[i].r);
27         sort(node,node+n,cmp);
28         enforcer.push(node[0]);
29         for(int i=1;i<n;i++)
30         {
31             Node now=enforcer.top();
32             if(node[i].l<=now.r) enforcer.push(node[i]);
33             else
34             {
35                 enforcer.pop();
36                 now.l=node[i].l, now.r=node[i].r;
37                 enforcer.push(now);
38             }
39         }
40 
41         printf("Case %d: %d
",++kase,enforcer.size());
42     }
43 }