贪心算法：会场安排问题（C语言实现）

会场安排问题

假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。对于给定的k个待安排的活动，计算使用最少会场的时间表。

问题分析：

这是一个活动安排问题，为了尽可能少地使用会场，就要尽可能多地在会场中安排活动。对于此类安排争用某一公共资源的问题使用贪心算法解决较为合适。

---

下面以k = 5（即有5个活动）为例用C语言实现以上过程。

活动起始时间分别为：

1 23        12 28        25 35        27 80        36 35

#include<stdio.h>
#include<stdlib.h>

//把各个活动的起始时间和结束时间按结束时间非减序排序
void sort(int n,int f[])
{
    int tempa,i,j;
    for(i=1; i<=n; i++)
    {
        for(j=i+1; j<=n; j++)
        {
            if(f[i]>f[j])
            {
                tempa=f[i];
                f[i]=f[j];
                f[j]=tempa;

            }
        }
    }
}

//贪心算法
int GreedySelect(int n,int s[],int f[],bool A[])
{
    A[1]=true;//将第一个活动先安排
    int i;
    int j=1;//j为刚刚被选中的活动的编号
    int count=1; //count为被安排的节目个数
    for(i=2; i<=n; i++)
    {
        if(s[i]>=f[j])
        {
            A[i]=1;
            j=i;
            count++;
        }
        else A[i]=0;

    }
    return count;
}

int main()
{
    int n,s[50],f[50];
    bool A[50];
    printf("请输入活动数：");
    scanf("%d",&n);
    printf("请依次输入节目开始结束的时间：") ;
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&s[i]);
        scanf("%d",&f[i]);
    }
    sort(n,f);
    printf("最少会场数为:%d",GreedySelect(n,s,f,A));
    return 0;
}

运行结果如下图：