贪心算法 — 例题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<bits/stdc++.h>
using namespace std;
const int maxn = 10010;
struct Node
{
    int begin, end;
}node[maxn];
bool cmp(Node a, Node b)
{
    return a.end < b.end;
}
int main()
{
    int t, n;  //t组数据,每组n个活动
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        for(int i=0; i<n; ++i)  //输入区间,并作简单处理
        {
            scanf("%d %d", &node[i].begin, &node[i].end);
            node[i].end++; //将区间变成左闭右开,便于处理
        }
        sort(node, node+n, cmp); //将区间按照右端点排序,右端点小的在前面
        int ans = 0;
        int pos = 0;
        for(int i=0; i<n; ++i)
        {
            if(node[i].begin>=pos)
            {
                ans++;
                pos = node[i].end;
            }
        }
        printf("%d\n", ans);
    }
    system("pause");
    return 0;
}

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

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