问题描述

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

思路

一个不相交的子集合，经典贪心问题。

寻找贪心的点：你可以贪心时长，越短越好；也可以贪心结束时间或者开始时间之类的。我们这里采取贪心结束时间和时长，就是越早结束越好，如果一起结束，那就选时间最短的。
步骤如下：

Step1 以结束时间为主要关键字，开始时间为次要关键字排序

Step2 直接把第一个定为起始活动

Step3 遍历并判断与已经在队列中的数值是否相容  

经典贪心在此是可以得到最优解的，只需证明：

 对于排序后的序列，一定存在一种最优解包括第一个活动（最早结束，时间最短）；
 说明活动选择问题具有优化子结构；
 算法按照Greedy 选择性计算解；

 代码

#include<bits/stdc++.h>
using namespace std;

struct activity{
    int start, end;
};

bool cmp(const activity &a,const activity &b)
{
    if(a.end!=b.end)
        return a.end<b.end;
    else
        return a.start>b.start;
}

int main(){
    int n;
    scanf("%d", &n);
    int satrt[n], end[n], dp[n];
    struct activity a[n];
    for(int i=0;i<n;i++)
        scanf("%d",&a[i].start);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i].end);
    sort(a,a+n,cmp);
    for (int i = 0;i<n;i++){
        printf("%d\t%d\n",a[i].start, a[i].end);
    }
    int now_end = a[0].end;
    int len = 1;
    for(int i=1;i<n;i++){
        if (a[i].start>now_end){
            now_end = a[i].end;
            len++;
        }
        printf("%d\t", now_end);
    }
    printf("%d", len);
    return 0;
} 

//测试数据：
//11
//1 3 0 5 3 5 12 2 8 8 6
//4 5 6 7 7 9 14 13 12 11 10

 

原文地址：http://www.cnblogs.com/kuailest/p/16907472.html

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！ 2. 分享目的仅供大家学习和交流，请务用于商业用途! 3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！ 4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！ 5. 如有链接无法下载、失效或广告，请联系管理员处理！ 6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！ 7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！ 8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载 声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性