概述
算法分析与设计
最大相容子集问题
问题描述：
有n项活动申请使用同一个礼堂，每项活动有一个开始时间和一个截至之间。如果任何两个活动不能同时进行，问如何选择这些活动，从而使得被安排的活动数量达到最多。
算法
按照截止时间从小到大排序，之后从前往后挑选。
核心代码：
int Greedy() {
int num=1;
sort(a+1,a+n+1,comp);
int temp=0;
cout<<a[1].i;
for(int i=2;i<=n;i++){
if(a[i].s>=a[temp].f){
num++;
temp=i;
cout<<" "<<a[temp].i;
}
}
cout<<"n";
return num;
}
时间复杂度：
算法的时间复杂度为O(n)。
源码：
https://github.com/SpiritDemon-max/myText/blob/master/Greedy.cpp
最后
以上就是义气茉莉为你收集整理的算法分析与设计 贪心值之最大相容子集问题算法分析与设计的全部内容，希望文章能够帮你解决算法分析与设计 贪心值之最大相容子集问题算法分析与设计所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
![C语言【微项目11】—活动安排问题[求解元素最多的相容活动子集]（采用贪心算法思想实现）【2021-12-11】一、Txsf.c二、 运行结果示例](/uploads/reation/bcimg11.png)
发表评论 取消回复