会场安排问题

问题描述：假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。

输入示例：5                                         输出：3

                    1 23

                    12 28

                     25 35

                     27 80

                     36  50

算法思想：用贪心算法解决这个问题，贪心算法：贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。也就是说，它总是做出局部最优解，寄希望于通过局部最优解来获得全局最优解。

一个活动的安排，取决于该活动的开始时间和上一个活动的结束时间是否冲突。所以先按照活动的结束时间将所有活动进行排序。然后循环安排活动，循环一遍，尽可能安排最多活动，只要时间不冲突，就在同一个会场，接下来再循环一遍，安排剩下的活动，又是一个会场，直到所有活动都被安排完。

代码：

#include<stdio.h>

struct node{

        int begin;

        int end;

        int flag;//标记活动是否被安排，0表示未安排，1表示以安排

};

int main(){

    int i,j,n;

    struct node temp,t[100];

    scanf("%d",&n);

    //输入活动的开始及结束时间

    for(i=0;i<n;i++){

        scanf("%d%d",&t[i].begin,&t[i].end);

        t[i].flag=0;

     }

//将活动以结束时间进行递增排序（简单选择）

for(i=0;i<n;i++){

    for(j=i+1;j<n;j++){

        if(t[i].end>t[j].end){

            temp.end=t[i].end;

            t[i].end=t[j].end;

            t[j].end=temp.end;

            }

        }

}

    int sum;//总共需要的会场数目

    int count;//当前以安排的活动数目

    while(count<n){

            int end_time=0;

            for(i=0;i<n;i++){

                    if(t[i].begin>end_time&&t[i].flag==0){

                        count++;

                        t[i].flag=1;

                        end_time=t[i].end;

            }

        }

    sum++;

    }

    printf("%d",sum);

}

运行截图：