贪心算法 --- 例题1.活动安排问题

一.问题描述

n个活动的集合E={1,2,…,n},在某一时间内要独占使用某个资源。每个活动i使用资源的起始时间为Si，终止时间为Fi。

活动i和活动j相容：是指[Si,Fi)与[Sj,Fj)不相交，即：Sj>=Fi 或Si>=Fj, 要求尽可能多地安排活动。即从活动集合E中选出最大相容活动子集。

二.解题思路

思路：最早结束的活动，优先安排。对f1,f2,…,fn从小到大排序 , 时间O(n log n);
即将n个活动按照结束时间非降序排列,依次考虑活动i,若i与已选择的活动相容,则将其加入相容活动子集.

Fj总是当前活动集合中结束最晚的活动
一旦Si>=Fj，则活动i和活动j相容，将活动i加入A中， i取代j成为最近加入的活动
直观上，该算法每次总是选取最早完成时间的活动，这样就为安排其它活动留下尽可能多的时间，从而能安排更多的活动。

证明上述贪心算法一定能得到最优解:(略) 数学归纳法得证.

代码如下:

// 活动安排问题
// 贪心算法
// 策略：每选一个之后能给后面的留更多的时间（效果：按结束时间排序）
#include
using namespace std;
const int maxn = 10010;
struct Node
{
    int begin, end;
    int index;  //记录活动起始编号
}node[maxn];
bool cmp(Node a, Node b)
{
    return a.end < b.end;
}
int main()
{
    int t, n;  //t组数据,每组n个活动
    cout<<"请输入数据组数:";
    scanf("%d", &t);
    while(t--)
    {
        cout<<"请输入活动个数:";
        scanf("%d", &n);
        cout<<"请输入每个活动的起始时间:"< select;
        for(int i=0; i=pos)
            {
                ans++;
                pos = node[i].end;
                select.push_back(node[i].index);
            }
        }
        printf("最多安排%d个活动\n", ans);
        printf("选中的活动为:");
        for(int x:select) printf("%d:[%d,%d] ",x, node[x].begin, node[x].end-1);
        cout<

运行结果:

参考毕方明老师《算法设计与分析》课件.

欢迎大家访问个人博客网站---乔治的编程小屋,和我一起努力吧!