活动安排问题(贪心)

蔚落 2022-05-15 02:40 251阅读 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 这一点要想明白

**下面给出了一组比较好的测试数据可以检验你写的代码是否正确：**  
![这里写图片描述][70]  
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;
    }

[70]: /images/20220515/07ad1d2fea504b68a3619557dc04834e.png