算法分析与设计-第10次作业-贪心算法-相容问题

1、问题

2、解析

定义结构体-活动：id号，开始时间，截止时间
使用堆排序对活动的截止时间进行排序
设置集合将相容的活动加进集合中相容的条件是，
前一个选进的活动的截至时间<新的准备加进集合的活动的开始时间（贪心策略）
给出输入案例：
n=10//10个活动
1 1 4//活动的id,开始时间，截止时间
2 3 5
3 2 6
4 5 7
5 4 9
6 5 9
7 6 10
8 8 11
9 8 12
10 2 12
输出选进活动的总数，每个选进活动的id,开始时间和截止时间

3、设计
struct item {
int id; //活动编号
int start;//活动开始时间
int end;//活动截至时间
};
int main() {
int n;//活动个数
int maxsize = 1;//最多有多少个活动
int ei;//初始截至时间
struct item act[100];
struct item x[100];
int id = 0;
scanf_s("%d", &n);
for (int i = 0; i < n; i++) {
scanf_s("%d %d %d", &act[i].id, &act[i].start, &act[i].end);
}
//将截止时间进行堆排序
heapsort(act, n);
ei = act[0].end;
x[id] = act[0];
//判断是否加入活动中
for (int i = 1; i <= n - 1; i++) {
if (act[i].start > ei) {
maxsize++;
x[++id] = act[i];
ei = act[i].end;
}
}
printf("%d\n", maxsize);
for (int i = 0; i < maxsize; i++) {
printf("%d %d %d\n", x[i].id, x[i].start, x[i].end);
}
}

4、分析

O(n)

5、源码

源码地址：https://github.com/ACynj/greedy.git