活动安排问题(贪心)-蒲公英云

活动安排问题(贪心)

蔚落 2022-05-15 02:40 396阅读 0赞

活动安排问题(贪心)

有若干个活动，第i个开始时间和结束时间是[Si,fi)，同一个教室安排的活动之间不能交叠，求要安排所有活动，最少需要几个教室？
Input
第一行一个正整数n (n <= 10000)代表活动的个数。
第二行到第(n + 1)行包含n个开始时间和结束时间。
开始时间严格小于结束时间，并且时间都是非负整数，小于1000000000
Output
一行包含一个整数表示最少教室的个数。
Sample Input
3
1 2
3 4
2 9
Sample Output
2
1.1
分析：

**最大区间不相交问题**题目中给的数据太水了 一开始没有完全理解题目的意思 应该是每选择一次 都要整体遍历一次有没有符和要求的 设置两个变量 start end 注意是按照start升序排序,而不是按照end 这一点要想明白

下面给出了一组比较好的测试数据可以检验你写的代码是否正确：
这里写图片描述
1.2
刚开始想的错误代码的核心

t=a[0].e;
      for(i=1;i<n;i++)
        {
            if(a[i].s>=t)
             { count=count;t=a[i].e;//错误在于每次只比较下一个是否符合要求 而不看总体有没有符合要求的
             }
             else count++;
        }

1.3
修改之后的核心代码：

for(i=0;i<n;i++)
        {
            if(b[i]==0)
            {
   count++;
             t=p[i].end;
             for(j=i+1;j<n;j++)
              if(p[j].start>=t&&b[j]==0)
              {
                count=count;
                t=p[j].end;
                b[j]=1;
              } 
            }
        }

1.4
代码总览：

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
struct node{
    int start;
    int end;
}p[100000];
int cmp(node a,node b)
{
    if(a.start==b.start)
    return a.end<b.end;
    return a.start<b.start;
}
int main()
{
    int n,i,j,t;
    while(scanf("%d",&n)!=EOF){
        for(i=0;i<n;i++)
        scanf("%d %d",&p[i].start,&p[i].end);
        sort(p,p+n,cmp);
        int b[100000]={
   0};
        int count=0;
        for(i=0;i<n;i++)
        {
            if(b[i]==0)
            {count++;
             t=p[i].end;
             for(j=i+1;j<n;j++)
              if(p[j].start>=t&&b[j]==0)
              {
                count=count;
                t=p[j].end;
                b[j]=1;
              } 
            }
        }
        printf("%d\n",count);
    }
    return 0;
}