贪心 ---活动安排问题

xiaoxiao2021-03-01  37

                                        活动安排问题

                                                                         来源: 51Nod - 1428

有若干个活动,第i个开始时间和结束时间是[Si,fi),同一个教室安排的活动之间不能交叠,求要安排所有活动,最少需要几个教室? 

Input

第一行一个正整数n (n <= 10000)代表活动的个数。 第二行到第(n + 1)行包含n个开始时间和结束时间。 开始时间严格小于结束时间,并且时间都是非负整数,小于1000000000

Output

一行包含一个整数表示最少教室的个数。

Sample Input

3 1 2 3 4 2 9

Sample Output

2

看代码 解释的挺详细了。

#include<stdio.h> #include<algorithm> #include<string.h> using namespace std; struct node { int b; //开始时间 int e; //结束时间 } p[10005]; int cmp(node x,node y) { if(x.b==y.b) return x.e<y.e; //排序 如果开始时间相同 那么按照结束时间从小到大排序 else return x.b<y.b; } int main() { int n; scanf("%d",&n); int i,j; int room[10005]; // 记录教室个数 memset(room,0,sizeof(room)); for(i=0; i<n; i++) { scanf("%d%d",&p[i].b,&p[i].e); } sort(p,p+n,cmp); int maxl=p[0].e; int sum=1; int flag=0; for(i=1; i<n; i++) { if(p[i].b>=maxl) { // 如果下一个活动的时间比上一个活动结束时间 晚 maxl=p[i].e; //安排一个教室,并且把结束时间更新 } else { flag=0; for(j=1; j<sum; j++) { if(p[i].b>=room[j]) { //遍历其他的房间看看可不可以安排 room[j]=p[i].e; //可以安排 更新结束时间 flag=1; break; } } if(flag==0) { //flag==0 代表没有教室可以安排,所以需要加一个教室 room[sum++]=p[i].e; //并把这个活动的结束时间放到数组中 } } } printf("%d\n",sum); //sum 代表了所需要的教室数 return 0; }

 

转载请注明原文地址: https://www.6miu.com/read-4550036.html

最新回复(0)