papamelon 212. 区间调度问题(挑战程序设计竞赛)
2021/11/28 1:10:26
本文主要是介绍papamelon 212. 区间调度问题(挑战程序设计竞赛),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
地址 https://www.papamelon.com/problem/212
解答
贪心算法
选择符合条件中区间结束比较早的那个区间。
可以证明,同样的选择区间中,选择较早结束的区间至少不会得到比选择较晚结束的区间更差的结果。
基于以上规则,我们将区间按照结束时间排序。
每次选择起始时间比当前结束时间小的区间,该区间是可以选择的区间中结束时间最早的。即可
// 1123555.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。 // #include <iostream> #include <algorithm> using namespace std; /* 5 1 99 2 5 4 7 6 9 8 10 输出 3 */ const int N = 100010; struct Node { int l; int r; }node[N]; int n; bool cmp(const struct Node& a, const struct Node& b) { return a.r < b.r; } void solve() { sort(node, node + n, cmp); int currEnd = -9999999; int ans = 0; for (int i = 0; i < n; i++) { if (currEnd < node[i].l) { ans++; currEnd = node[i].r; } } cout << ans << endl; return ; } int main() { while (cin >> n) { for (int i = 0; i < n; i++) { int a, b; cin >> a >> b; if (a > b) { swap(a, b); } node[i].l = a; node[i].r = b; } solve(); } return 0; }
我的视频题解空间
这篇关于papamelon 212. 区间调度问题(挑战程序设计竞赛)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm,再安排pandas等模块,说是没有打包工具?
- 2024-05-29java11新特性
- 2024-05-29哪些无用敏捷指标正在破坏敏捷转型?
- 2024-05-29鸿蒙原生应用再新丁!新华社 入局鸿蒙
- 2024-05-29设计模式 之 迭代器模式(Iterator)