贪心算法解决活动安排问题

记录一下今年考研算法题最后一道压轴题以及个人解法（大佬勿喷）

问题题目

设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si <fi 。如果选择了活动i，则它在半开时间区间[si, fi)内占用资源。若区间[si, fi)与区间[sj, fj)不相交，则称活动i与活动j是相容的。也就是说，当si≥fj或sj≥fi时，活动i与活动j相容。

算法分析：

输入：

输入正整数n，随后分别输入n个活动的开始时间begin和结束时间end。

核心：

首先，先将begin和end数组按照结束时间升序排列（一定是得按照结束时间升序排列才是最优解，我考试写的是按照开始时间升序排列，脑子抽风了，然后就大错特错了，太痛了…）然后，后面就是每次总是选择具有最早完成时间的相容活动加入集合set中，最后输出结果

c语言源码：

#include <stdio.h>

int main()
{
    int n,i,j,k,tmp;
    scanf("%d", &n);
    int begin[n+1];
    int end[n+1];
    int set[n+1];
    for (i=1; i<=n; i++)
    {
        set[i] = 0; //初始化活动安排数组
        scanf("%d%d", &begin[i],&end[i]); //输入各个互动开始结束时间
    }
    //对各个活动按照结束时间升序排列（选择排序）
    for (i=1; i<n; i++)
    {
        k=i;
        for (j=i+1; j<=n; j++)
        {
            //按照结束时间升序排列
            if(end[j] < end[k])
                k = j;
        }
        if (i!=k)
        {
            tmp = begin[i];
            begin[i] = begin[k];
            begin[k] = tmp;
            tmp = end[i];
            end[i] = end[k];
            end[k] = tmp;
        }
    }
    set[1] = 1; //先将第一个活动安排
    j = 1; //表示当前最后安排的活动的序号
    int count=1;    //表示已安排活动的数量
    for (i=2; i<=n; i++)    //从第二个活动开始安排
    {
        if (begin[i] >= end[j]) //如果当前活动开始时间在上一个活动结束时间之后
        {
            set[i] = 1; //将当前活动安排进去
            j = i;  //最后一个活动为当前活动
            count++;    //已安排活动数+1
        }
    }
    for (i=1; i<=n; i++)
    {
        if (set[i]==1)
        {
            printf("第%d个活动从%d点到%d点\n", i, begin[i],end[i]);
        }
    }
    printf("\n一共安排了%d个活动",count);
    return 0;
}

输入

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

输出

第1个活动从1点到4点
第4个活动从5点到7点
第8个活动从8点到11点
第11个活动从12点到14点

一共安排了4个活动