贪心算法求解畜栏问题
求解畜栏问题
题目内容：
有n头牛（1<=n<=50,000)要挤奶。给定每头牛挤奶的时间区间[A,B]，1<=A<=B<=1,000,000，A,B为整数。牛需要呆在畜栏里才能挤奶。一个畜栏同一时间只能容纳一头牛。问至少需要多少个畜栏，才能完成全部挤奶工作，以及每头牛都放哪个畜栏里？注意：在同一个畜栏的两头牛，它们挤奶时间区间不能在端点重合。
输入格式:
第1行：一个正整数N；
第2…N+1行：第i+1行的两个整数给出第i头奶牛的挤奶时间。
输出格式：
第1行：需要畜栏的最小数；
第2…N+1行：第i+1行表示第i头奶牛被分配到的畜栏序号
输入样例：
5
1 10
2 4
3 6
5 8
4 7
输出样例：
4
1
2
3
2
4
using namespace std;typedef struct {int begin;int end;int number;int NO;bool f;}cow;cow a[50000];int minNumber=0;bool compare1(cow c1,cow c2){if(c1.end<=c2.end) return true;else return false;}bool compare2(cow c1,cow c2){if(c1.NO<c2.NO) return true;else return false;}void getCorril(int n){sort(a+1,a+n+1,compare1);bool flag=false;//还有牛未分配while(!flag){minNumber++;int foreend=0;flag=true;for(int i=1;i<=n;i++){if(a[i].begin>foreend&&a[i].number==0){a[i].number=minNumber;flag=false;foreend=a[i].end;}}}}int main(){int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d%d",&a[i].begin,&a[i].end);a[i].number=0;a[i].NO=i;a[i].f=false;}getCorril(n);printf("%d\n",minNumber-1);sort(a+1,a+n+1,compare2);int count=0;//这番操作只是为了解决先输入的信息的牛占据编号小的畜栏这个**的问题for(int i=1;i<=n;i++){if(!a[i].f){int m=a[i].number;a[i].number=++count,a[i].f=true;for(int j=i+1;j<=n;j++){if(a[j].number==m&&a[j].f==false){a[j].number=count;a[j].f=true;}}}}for(int i=1;i<=n;i++) printf("%d\n",a[i].number);return 0;}