-
问题
相容问题，解析时给出其他几种贪心策略（如按开始时间从小到大、每个活动时间的占用时间等），并给出这些贪心策略无法实现最优的反例。
问题描述
有n项活动申请使用同一个礼堂，每项活动有一个开始时间和一个截止时间。如果任何两个活动不能同时举行，问如何选择这些活动,从而使得被安排的活动数量达到最多。 -
解析
[问题的理解和推导，可用电子版直接在此编写，也可用纸笔推导，拍照嵌入本文档]
建模：设S={1,2,…,n}为活动的集合，si和fi分别为活动i的开始和截止时间，i=1,2,…,n
定义：活动i和j相容 si>=fi或sj>=fi,i≠j
求S最大的两两相容的活动子集A。
按开始时间从小到大：
-
设计
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct huodong{int ss;int ee;int time;
}A[130];
void sort(huodong A[],int n) {for (int i = 0; i < n - 1; i++){for (int j = 1; j < n - i; j++){if (A[j - 1].end > A[j].end){int temp = A[j - 1].end;A[j - 1].end = A[j].end;A[j].end = temp;temp = A[j - 1].start;A[j - 1].start = A[j].start;A[j].start = temp;temp = A[j - 1].time;A[j - 1].time = A[j].time;A[j].time = temp;}}}
}
int f(huodong A[],int n) {int k = 1;int lastend = A[0].end;for (int i = 1; i < n; i++){if (A[i].start > lastend){k++;lastend = A[i].end;}}return k;
}
int main(){int l,pp;printf("请输入活动数目:");scanf("%d", &l);printf("请输入输入活动开始和结束时间:");for(pp = 0; pp < l; pp++){scanf("%d", &A[pp].ss);scanf("%d", &A[pp].ee);A[pp].time = A[pp].ee - A[pp].ss;}sort(A,l);printf("%d", f(A, l));
}
- 分析
时间复杂度：T(n)=O(n)
