问题描述

设有n个活动的集合E = {1, 2, 3, … n},其中每个活动都要求用同一资源,例如,演讲会场等。而在同一时间内只能有一个活动能够使用这个资源。每个活动资源i都有一个要求使用这一资源的起始时刻$$s_i和一个结束时刻 f_i $$,并且设定​$$ s_i < f_i $$。如果选择了活动i,那么它在半开区间[​$$ s_i , f_i $$)内占用资源,如果区间[​$$ s_i , f_i $$) 与 区间 [​$$ s_j f_j $$)不相交,则称活动i与活动j是相容的。也就是说,当​$$ s_i >= f_j $$ 或者 ​$$ s_j >= ​$$ f_i ​$$时,活动i与活动j是相容大的。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。试设计一算法实现之。

解题策略

策略1:活动开始早的优先

策略2:活动结束早的优先

策略3:活动持续时间短的优先

通过列举反例,我们不难发现,策略1和策略3都不是最优策略,因此我们按照策略2进行题解

  1. 初始化活动集合,并按照活动结束早的顺序对活动集里的活动进行排序
  2. 默认选择第1个活动,然后遍历每个活动,观察当前待选择的这个活动的开始时间是否 大于等于 前面刚刚选择活动的结束时间,如果满足,将该活动对应的下标的解向量置为1
  3. 遍历解向量,输出解向量为1的活动,就是我们要求的最大相容活动集合

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <stdio.h>
typedef struct
{
double s, f; //活动的开始时间和结束时间
} Activity;

Activity activity[10000];
int x[10000]; //解向量

void swap(Activity activity[], int index1, int index2)
{
Activity act = activity[index1];
activity[index1] = activity[index2];
activity[index2] = act;
}

int partition(Activity activity[], int low, int high)
{
Activity pivot = activity[low];
while(low < high){
while((low < high) && (pivot.f <= activity[high].f))
high--;
swap(activity, low, high);
while((low < high) && (pivot.f >= activity[low].f))
low++;
swap(activity, low, high);
}
return low;
}

void quickSort(Activity activity[], int low , int high)
{
if (low < high) {
int actNum = partition(activity, low, high);
quickSort(activity, low, actNum-1);
quickSort(activity, actNum+1, high);
}
}

void main()
{
int n;
printf("请输入活动的个数:");
scanf("%d", &n);
for(int i = 1; i <= n; i++)
{
printf("请输入活动%d的开始时间和结束时间:", i);
scanf("%lf %lf", &activity[i].s, &activity[i].f);
}

//按照活动结束时间对活动进行排序
quickSort(activity, 1, n);
x[1] = 1;
int temp = activity[1].f; //存储上一个选入活动的完成时间
for(int i = 2; i <= n; i++)
{
if (activity[i].s >= temp) {
x[i] = 1;
temp = activity[i].f;
}
else
x[i] = 0;
}

printf("选择的活动集合有:");
for(int i = 1; i <= n; i++)
{
if (x[i] == 1)
printf("%d\t", i);
}
}

参考

活动安排问题