嘉兴seo网站建设费用,十堰网站整站优化公司,热狗seo优化外包,网站建设公司果动问题: 给定n个活动#xff0c;每个活动有一个开始时间si和结束时间fi#xff0c;选择出最大的互不相容的活动 集合。 思路#xff1a; 将所有活动按照结束时间从小到大排序。 选择第一个活动#xff0c;并将其加入最终的选择集合中。 依次考虑剩余的活动#x…问题: 给定n个活动每个活动有一个开始时间si和结束时间fi选择出最大的互不相容的活动 集合。 思路 将所有活动按照结束时间从小到大排序。 选择第一个活动并将其加入最终的选择集合中。 依次考虑剩余的活动如果当前活动的开始时间晚于等于上一个已选活动的结束时间则将该活动加入最终的选择集合中。 重复步骤3直到所有活动都被考虑完毕。 输出最终的选择集合。 示例:
按照右端点从小到大排序后的顺序为 区间1: [1, 4] 区间2: [3, 6] 区间3: [5, 7] 按照区间调度算法进行选择具体步骤如下 首先选择右端点最小的区间1 [1, 4]更新preEnd为4。 接着剩下区间2 [3, 6] 的起始位置小于preEnd无法选择。 最后剩下的区间3 [5, 7] 的起始位置大于preEnd可以选择。 选中的区间序号为1和3选中的区间个数为2。 所以最优解是选择区间1和3。 代码:
#include iostream
#include vector
#include algorithmusing namespace std;int main() {// 读取活动数量int n;cin n;// 保存活动开始时间和结束时间的向量vectorpairint, int activities(n);// 读取每个活动的开始时间和结束时间for (auto activity : activities) {cin activity.first activity.second;}// 按活动结束时间对活动进行排序sort(activities.begin(), activities.end(), [](const auto a, const auto b) { return a.second b.second; });// 保存被选中的活动序号的向量vectorint selected;int lastEnd 0; // 上一个被选择活动的结束时间// 遍历排序后的活动列表选择不冲突的活动for (int i 0; i n; i) {// 如果当前活动的开始时间大于等于上一个被选择活动的结束时间// 则说明当前活动与上一个被选择活动不冲突可以选择if (activities[i].first lastEnd) {selected.push_back(i 1); // 将符合条件的活动序号加入selected向量lastEnd activities[i].second; // 更新上一个被选择活动的结束时间}}// 输出最大不相交活动集合的大小cout 最大不相交活动集合的大小 selected.size() endl;// 输出被选择的活动序号cout 被选择的活动序号;for (auto num : selected) {cout num ;}return 0;
} 运行程序 将测试用例输入程序。你可以在终端中手动输入活动数量以及每个活动的开始和结束时间或者将测试用例保存在文本文件中并使用文件重定向将其输入到程序中。
例如在终端中手动输入
