区间贪心算法-——活动安排问题

﹏ヽ暗。殇╰゛Y 2023-10-05 15:58 62阅读 0赞

## 问题题目 ##

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

**例如：有n个活动，第i个活动开始时间和结束时间是\[Si,fi)，只有一个教室，活动之间不能交叠，求最多安排多少个活动？**

**设待安排的11个活动的开始时间和结束时间如下表 (按结束时间的非减序排列)：**

<table> 
 <tbody> 
  <tr> 
   <td style="border-color:#000000;vertical-align:middle;width:52pt;"> <p><strong><span style="color:#000000;">i</span></strong></p> </td> 
   <td style="border-color:#000000;vertical-align:middle;width:53pt;"> <p><strong><span style="color:#000000;">1</span></strong></p> </td> 
   <td style="border-color:#000000;vertical-align:middle;width:52pt;"> <p><strong><span style="color:#000000;">2</span></strong></p> </td> 
   <td style="border-color:#000000;vertical-align:middle;width:53pt;"> <p><strong><span style="color:#000000;">3</span></strong></p> </td> 
   <td style="border-color:#000000;vertical-align:middle;width:52pt;"> <p><strong><span style="color:#000000;">4</span></strong></p> </td> 
   <td style="border-color:#000000;vertical-align:middle;width:52pt;"> <p><strong><span style="color:#000000;">5</span></strong></p> </td> 
   <td style="border-color:#000000;vertical-align:middle;width:53pt;"> <p><strong><span style="color:#000000;">6</span></strong></p> </td> 
   <td style="border-color:#000000;vertical-align:middle;width:52pt;"> <p><strong><span style="color:#000000;">7</span></strong></p> </td> 
   <td style="border-color:#000000;vertical-align:middle;width:52pt;"> <p><strong><span style="color:#000000;">8</span></strong></p> </td> 
   <td style="border-color:#000000;vertical-align:middle;width:53pt;"> <p><strong><span style="color:#000000;">9</span></strong></p> </td> 
   <td style="border-color:#000000;vertical-align:middle;width:52pt;"> <p><strong><span style="color:#000000;">10</span></strong></p> </td> 
   <td style="border-color:#000000;vertical-align:middle;width:53pt;"> <p><strong><span style="color:#000000;">11</span></strong></p> </td> 
  </tr> 
  <tr> 
   <td style="border-color:#000000;vertical-align:middle;width:52pt;"> <p><strong><span style="color:#000000;">s[i]</span></strong></p> </td> 
   <td style="border-color:#000000;vertical-align:middle;width:53pt;"> <p><strong><span style="color:#000000;">1</span></strong></p> </td> 
   <td style="border-color:#000000;vertical-align:middle;width:52pt;"> <p><strong><span style="color:#000000;">3</span></strong></p> </td> 
   <td style="border-color:#000000;vertical-align:middle;width:53pt;"> <p><strong><span style="color:#000000;">0</span></strong></p> </td> 
   <td style="border-color:#000000;vertical-align:middle;width:52pt;"> <p><strong><span style="color:#000000;">5</span></strong></p> </td> 
   <td style="border-color:#000000;vertical-align:middle;width:52pt;"> <p><strong><span style="color:#000000;">3</span></strong></p> </td> 
   <td style="border-color:#000000;vertical-align:middle;width:53pt;"> <p><strong><span style="color:#000000;">5</span></strong></p> </td> 
   <td style="border-color:#000000;vertical-align:middle;width:52pt;"> <p><strong><span style="color:#000000;">6</span></strong></p> </td> 
   <td style="border-color:#000000;vertical-align:middle;width:52pt;"> <p><strong><span style="color:#000000;">8</span></strong></p> </td> 
   <td style="border-color:#000000;vertical-align:middle;width:53pt;"> <p><strong><span style="color:#000000;">8</span></strong></p> </td> 
   <td style="border-color:#000000;vertical-align:middle;width:52pt;"> <p><strong><span style="color:#000000;">2</span></strong></p> </td> 
   <td style="border-color:#000000;vertical-align:middle;width:53pt;"> <p><strong><span style="color:#000000;">12</span></strong></p> </td> 
  </tr> 
  <tr> 
   <td style="border-color:#000000;vertical-align:middle;width:52pt;"> <p><strong><span style="color:#000000;">f[j]</span></strong></p> </td> 
   <td style="border-color:#000000;vertical-align:middle;width:53pt;"> <p><strong><span style="color:#000000;">4</span></strong></p> </td> 
   <td style="border-color:#000000;vertical-align:middle;width:52pt;"> <p><strong><span style="color:#000000;">5</span></strong></p> </td> 
   <td style="border-color:#000000;vertical-align:middle;width:53pt;"> <p><strong><span style="color:#000000;">6</span></strong></p> </td> 
   <td style="border-color:#000000;vertical-align:middle;width:52pt;"> <p><strong><span style="color:#000000;">7</span></strong></p> </td> 
   <td style="border-color:#000000;vertical-align:middle;width:52pt;"> <p><strong><span style="color:#000000;">8</span></strong></p> </td> 
   <td style="border-color:#000000;vertical-align:middle;width:53pt;"> <p><strong><span style="color:#000000;">9</span></strong></p> </td> 
   <td style="border-color:#000000;vertical-align:middle;width:52pt;"> <p><strong><span style="color:#000000;">10</span></strong></p> </td> 
   <td style="border-color:#000000;vertical-align:middle;width:52pt;"> <p><strong><span style="color:#000000;">11</span></strong></p> </td> 
   <td style="border-color:#000000;vertical-align:middle;width:53pt;"> <p><strong><span style="color:#000000;">12</span></strong></p> </td> 
   <td style="border-color:#000000;vertical-align:middle;width:52pt;"> <p><strong><span style="color:#000000;">13</span></strong></p> </td> 
   <td style="border-color:#000000;vertical-align:middle;width:53pt;"> <p><strong><span style="color:#000000;">14</span></strong></p> </td> 
  </tr> 
 </tbody> 
</table>

## 算法分析： ##

由于输入的活动以其完成时间的非减序排列，所以算法greedySelector每次总是选择具有最早完成时间的相容活动加入集合A中。该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。 算法greedySelector的效率极高。当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用O(nlogn)的时间重排。

## c语言源码： ##

#include<stdio.h>
    #include<stdlib.h>
    #include<algorithm>
    using namespace std;
    #define max 1000
    
    int greedselect(int a[],int b[],bool t[],int n){
        int i,j=0,cnt=1;	
    	t[0]=1;
    	printf("(%d,%d)\n",a[0],b[0]);
    	for(i=1;i<n;i++){   //每次选择当前的左区间与上一个的右区间进行比较
    		if(a[i]>b[j]){   //如果当前的左区间大于上一个的右区间，则加入到活动中
    		  t[i]=1;
    		  printf("(%d,%d)\n",a[i],b[i]);
    		  cnt++;
    		  j=i;
    		}
    	}
    	return cnt;
    }
    
    int main(){
     int k,n,cont;
     bool t[max];
     int a[max],b[max];
     scanf("%d",&n);
    for(k=0;k<n;k++){
       scanf("%d%d",&a[k],&b[k]);
       t[k]=0;
    }
    //memset(t,0,sizeof(t));//这里初始化t数组可以用memset函数
    cont=greedselect(a,b,t,n);
    printf("%d",cont);
    
    return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，62人围观）

还没有评论，来说两句吧...

相关阅读

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

活动安排问题--贪心算法目录活动安排问题--贪心算法 -------------------- 本文章向大家介绍活动安排问题--贪心算法，主要内容包括其使用实例

墨蓝/ 2024年03月27日 19:02/ 0 赞/ 91 阅读

相关贪心 1428 活动安排问题

[1428 活动安排问题][1428] 基准时间限制：1 秒空间限制：131072 KB 分值: 10 [难度：2级算法题][2] 有若干个活动，第i个开始时间和结束时间

一时失言乱红尘/ 2024年02月18日 23:16/ 0 赞/ 67 阅读

相关 pzhu 1082: 活动安排问题（贪心）

1082: 活动安排问题 Description 我们都知道经典的活动安排问题是这样描述的：设有n个活动的集合E=\{1,2,…,n\}，其中每个活动都要求使用同一

Love The Way You Lie/ 2024年02月17日 21:41/ 0 赞/ 14 阅读

相关 [C++] 贪心算法之活动安排、背包问题

一、贪心算法的基本思想　　在求解过程中，依据某种贪心标准，从问题的初始状态出发，直接去求每一步的最优解，通过若干次的贪心选择，最终得出整个问题的最优解。　　从贪心算

男娘i/ 2023年10月06日 09:41/ 0 赞/ 13 阅读

相关区间贪心算法-——活动安排问题

问题题目设有n个活动的集合E=\{1,2,…,n\}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用

﹏ヽ暗。殇╰゛Y/ 2023年10月05日 15:58/ 0 赞/ 63 阅读

相关算法设计与分析——贪心算法——活动安排问题

问题描述：设有n个活动的集合E=\{1,2,…,n\}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用

た入场券/ 2023年01月15日 08:09/ 0 赞/ 269 阅读

相关贪心算法解决活动安排问题

4.2 活动安排问题设有n个活动的集合E=\{1, 2, …, n\}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个

青旅半醒/ 2022年06月07日 04:35/ 0 赞/ 325 阅读

相关活动安排（贪心）

问题：有n个活动的集合A=\{1,2,…,n\}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。求解：安排尽量多项活动在该场地进

本是古典何须时尚/ 2022年06月06日 12:20/ 0 赞/ 248 阅读

相关活动安排问题(贪心)

活动安排问题(贪心) 有若干个活动，第i个开始时间和结束时间是\[Si,fi)，同一个教室安排的活动之间不能交叠，求要安排所有活动，最少需要几个教室？ Input

蔚落/ 2022年05月15日 02:40/ 0 赞/ 266 阅读

相关贪心算法（1）：活动安排问题

题目设有n个活动的集合E＝\{1，2，…，n\}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源每个活动i都有一个要求使用该资源

悠悠/ 2022年02月05日 10:21/ 0 赞/ 390 阅读