贪心算法: 区间选点
2022/7/13 14:21:40
本文主要是介绍贪心算法: 区间选点,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
c++
区间选点
/* 区间选点 题目描述: 题目搬运: 给定 N 个闭区间 [ai, bi],请你在数轴上选择尽量少的点,使得每个区间内至少包含一个选出的点。 输出选择的点的最小数量。 位于区间端点上的点也算作区间内。 输入格式: 第一行包含整数 N,表示区间数。 接下来 N 行,每行包含两个整数 ai,bi,表示一个区间的两个端点。 输出格式: 输出一个整数,表示所需的点的最小数量。 数据范围: 1 ≤ N ≤ 10^5, −10^9 ≤ ai ≤ bi ≤ 10^9 解题思路: 本题是一个非常典型的贪心问题,关键是如何寻找正确的贪心思路。 1. 首先,先对区间升序排序,左端点作为第一关键字,右端点作为第二关键字,然后我们思索如何贪心 2. 数组排序之后,我们需要明确一个目标,在不漏下左边任何一个区间的前提下,将第一个点尽可能的向右 因为,左面不存在遗漏区间时,点越向右越可能覆盖更多的区间。 但是如何实现在 不漏下左边任何一个区间的前提下,将选点尽可能的靠右 在遍历已经排序的区间 segments 时,在当前已选择的 点 point 上更新, min(point, segments[i].right) 而且当 point > segments[i].left, 说明以后的区间 都不会和 point 有交集了,而且此轮的 Point 也一定不会被更新了, 因为 segments[i].left <= sigments[i].right 3. 重复执行 2 操作,直到区间便利完毕。 */ #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <queue> #include <cmath> using namespace std; typedef pair<int, int> PII; const int N = 100010, _INF = 0xcfcfcfcf, INF = 0x3f3f3f3f; PII segments[N]; int n; bool cmp(PII t1, PII t2) { if (t1.first == t2.first) { return t1.second < t2.second; } else { return t1.first < t2.first; } } int main() { // input scanf("%d", &n); for (int i = 1; i <= n; i ++ ) { scanf("%d%d", &segments[i].first, &segments[i].second); } // sort and greedy algorithm int cur_min = _INF; sort(segments + 1, segments + n + 1); int cnt = 0; for (int i = 1; i <= n; i ++ ) { if (cur_min == _INF) { cur_min = segments[i].second; } else if (segments[i].first > cur_min) { cnt += 1; cur_min = segments[i].second; } else { cur_min = min(cur_min, segments[i].second); } } // 补上去最后一个 cnt += 1; printf("%d\n", cnt); return 0; }
这篇关于贪心算法: 区间选点的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?