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

活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合,是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。

  设有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相容。

  由于输入的活动以其完成时间的非减序排列,所以算法greedySelector每次总是选择具有最早完成时间的相容活动加入集合A中。直观上,按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说,该算法的贪心选择的意义是使剩余的可安排时间段极大化,以便安排尽可能多的相容活动。

  此算法的效率极高。当输入的活动已按结束时间的非减序排列,算法只需O(n)的时间安排n个活动,使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列,可以用O(nlogn)的时间重排。

  贪心算法并不总能求得问题的整体最优解。但对于活动安排问题,贪心算法却总能求得的整体最优解,即它最终所确定的相容活动集合A的规模最大。这个结论可以用数学归纳法证明。

算法模版:

template <class Type>
void GreedySelector(int n,Type s[],Type f[],bool A[])
{
    A[1] = true;
    int j=1;
    for(int i=2;i<=n;i++)
    {
        if(s[i]>=f[j])
        {
            A[i] = true;
            j=i;
        }
        else
            A[i] = false;
    }
}

应用实例:

问题描述:

Problem Description
“今年暑假不AC?”
“是的。”
“那你干什么呢?”
“看世界杯呀,笨蛋!”
“@#$%^&*%...”

确实如此,世界杯来了,球迷的节日也来了,估计很多ACMer也会抛开电脑,奔向电视了。
作为球迷,一定想看尽量多的完整的比赛,当然,作为新时代的好青年,你一定还会看一些其它的节目,比如新闻联播(永远不要忘记关心国家大事)、非常6+7、超级女生,以及王小丫的《开心辞典》等等,假设你已经知道了所有你喜欢看的电视节目的转播时间表,你会合理安排吗?(目标是能看尽量多的完整节目)
 

Input
输入数据包含多个测试实例,每个测试实例的第一行只有一个整数n(n<=100),表示你喜欢看的节目的总数,然后是n行数据,每行包括两个数据Ti_s,Ti_e (1<=i<=n),分别表示第i个节目的开始和结束时间,为了简化问题,每个时间都用一个正整数表示。n=0表示输入结束,不做处理。
 

Output
对于每个测试实例,输出能完整看到的电视节目的个数,每个测试实例的输出占一行。
 

Sample Input
12
1 3
3 4
0 7
3 8
15 19
15 20
10 15
8 18
6 12
5 10
4 14
2 9
0
 

Sample Output
5

代码:

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
typedef struct
{
        int s;
        int e;
}node;
int cmp(const void *a,const void *b)
{
    return ((node *)a)->e-((node *)b)->e;
}
int main()
{
      int n,i,j,c;
      node a[1000];
      while(scanf("%d",&n),n)
      {
              for(i=0;i<n;i++)
              scanf("%d%d",&a[i].s,&a[i].e);
              qsort(a,n,sizeof(a[0]),cmp); //按结束时间升序排列
              c=1;
              i=0;
              for(j=1;j<n;j++)
              {
                     if(a[j].s>=a[i].e) 
                     {
                         c++;
                         i=j;
                     }
              }
              printf("%d\n",c);
      }
       return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小L的魔法馆

第13届景驰-埃森哲杯广东工业大学ACM程序设计大赛--K-密码

2786
来自专栏牛客网

百度 提前批 大数据岗位 面经

【每日一语】这个世界,生活,人本身,都是荒诞的。不要白费心智去猜,去理论,因为无可猜,无可理论。事情并不一定要因为一个理由而发生,发生之后并不一定要达到什么目的...

1922
来自专栏生信宝典

小学生都学Python了,你还不知道怎么开始

最近Python又火了一把,一是我大山东省小学六年级的教材中加入了Python的内容;二是从2018年起,Python也将成为浙江高考的内容之一;三是计算机二级...

2399
来自专栏C语言及其他语言

本杰明·富兰克林会怎样学习编程?

来源:编程派 优秀的编程方法是极难教的。编程书籍大抵都是这样开头的:“这是X方法的例子,还有下面这个例子”。教教基础是容易的,因为基础知识也就那么多。难就难在...

37610
来自专栏维恩的派VNPIE

针对Quant的Python快速入门指南

最近有越来越多的朋友在知乎或者QQ上问我如何学习入门Python,就目前需求来看,我需要写这么一篇指南。

2904
来自专栏牛客网

18届秋招c++面试流水账

18届秋招部分流水账,c++开发方向。供春招参考 定义: - 为回答一般 +为较好 x为不会 【远景能源】【挂】 1面 笔试,手写一个编程题。剑指offer原题...

4058
来自专栏马哥教育

学不好Python?我们分析看看正确的学习方法是什么-马哥教育

提起对Python的印象,除了全能之外恐怕就是简单易学了。很多人都在推荐新手学Python入门,毕竟语法简单、语句简洁,所谓“人生苦短我用Python”绝不是一...

3905
来自专栏程序人生 阅读快乐

《算法心得 高效算法的奥秘 原书第2版》

由在IBM工作50余年的资深计算机专家撰写,Amazon全五星评价,算法领域最有影响力的著作之一

661
来自专栏大数据文摘

前沿 | 谷歌翻译最新突破,“关注机制”让机器读懂词与词的联系

1954
来自专栏DT数据侠

如何快速迈入高薪热门行业,这个技能需点亮!

提到人工智能 (AI) ,无疑是现今全球产业的“当红小生“;论流量,在媒体界也是“扛把子”级选手。从2017年的飞速发展,到如今2018已被称为人工智能元年,语...

870

扫码关注云+社区

领取腾讯云代金券