贪心算法——活动安排问题

设有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相容。
活动安排问题就是在所给的活动集合中选出最大的相容活动子集合。

---

解析：

初始定义

把活动的起始时间和结束时间定义为结构体：

struct action{
    int s;          //起始时间
    int f;          //结束时间
    int index;      //活动的编号
};

活动的集合E记为数组：
E ：action a[1000];
按活动的结束时间升序排序
排序比较因子：

bool cmp(const action &a, const action &b)
{
    if (a.f<=b.f) return true;
    return false;
}

使用标准模板库函数排序（下标0未用）：
sort(a, a+n+1, cmp);

算法

//形参数组b用来记录被选中的活动
void GreedySelector(int n, action a[], bool b[])
{
　　b[1] = true;　　　　　//第1个活动是必选的
　　//记录最近一次加入到集合b中的活动
　　int preEnd = 1;
　　for(int i=2; i<=n; i++)
　　　　if (a[i].s>=a[preEnd].f)
　　　　{
　　　　　　b[i] = true;
　　　　　　preEnd = i;
　　　　}
}

分析

活动i在集合b中，当且仅当b[i]的值为true。变量preEnd用来记录最近一次添加到集合b中的活动，也就是上一个已安排的活动。
算法GreedySelector首先选择活动(这里的活动1指按照结束时间升序排序后的第一个活动)，并将preEnd指针初始化为1，然后依次检查活动i是否与当前已经选择的所有活动相容。若相容则将活动i加入到集合b中，否则放弃，继续遍历剩余活动。
由于输入的活动按结束时间升序排序，所以算法GreedySelector每次总是选择具有最早完成时间的相容活动加入到集合b中。直观上，按照这种方法选择相容活动为未安排活动留下了尽可能多的时间。该算法的贪心选择意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。
最后根据数组b的值输出选中的活动编号。

样例数据 按照结束时间升序排序
活动安排问题的几何意义
贪心算法并不总能求得问题的整体最优解，但对于活动安排问题，贪心算法GreedySelector却总能求得整体最优解，即它最终所确定的相容内容活动集合b的规模最大。

代码

#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <string.h> 
using namespace std;

struct action{
    int s;
    int f;
    int index;
};

bool cmp(const action &a, const action &b)
{
    if (a.f<=b.f) return true;
    return false;
}


void GreedySelector(int n, action a[], bool b[])
{
    b[1] = true;
    int preEnd = 1;
    for(int i=2; i<=n; i++)
        if (a[i].s>=a[preEnd].f)
        {
            b[i] = true;
            preEnd = i;
        }
}

int main()
{
    int n;
    while(cin>>n && n)
    {
        action a[1000];
        bool b[1000];
        memset(b,false,sizeof(b));
        for(int i=1; i<=n; i++)
        {
            cin>>a[i].s>>a[i].f;
            a[i].index = i;
        }
        sort(a, a+n+1, cmp);
        GreedySelector(n, a, b);
        for(int i=1; i<=n;i++)
            if(b[i]) cout<<a[i].index<<" ";
        cout<<endl;
    }
    return 0;
}