AcWing 905. 区间选点
给定N个闭区间[ a i , b i ] ，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。
输出选择的点的最小数量。
位于区间端点上的点也算作区间内。
输入格式
第一行包含整数N，表示区间数。
接下来N行，每行包含两个整数ai,bi，表示一个区间的两个端点。
输出格式
输出一个整数，表示所需的点的最小数量。
思路
①将每个区间按右端点从小到大排序
②从前往后依次枚举每个区间
如果当前区间中已经包含点，则直接pass
否则，选择当前区间的右端点
证明上述方法是可行的：
cnt为所有可行解ans为可行解里的最小值 ∴ \therefore∴ans<=cnt
cnt个互不相交的区间 至少要有cnt个点 ∴ \therefore∴ans>=cnt
∴ \therefore∴ans=cnt
选最少的点 就要让一个点覆盖越多的区间 取右端点的话 就有更大的机会与后面的区间重合
#include<iostream> #include<cstdio> #include<queue> #include<string> #include<cstring> #include<map> #include<vector> #include<set> #include<stack> #include<algorithm> #include<vector> #include<utility> #include<deque> #define INF 0x3f3f3f3f #define mod 1000000007 #define endl '\n' #define eps 1e-6 inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } inline int lowbit(int x) { return x & -x; } using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; const int N = 100010; struct Range { int l, r; }range[N]; bool cmp(struct Range a, struct Range b) { return a.r < b.r; } int main() { int n;cin >> n; for (int i = 0; i <= n;++i) { int l, r; scanf("%d%d", &l, &r); range[i] = { l,r }; } sort(range, range + n, cmp); int res = 0, ed = -2e9; for (int i = 0;i < n;++i) { if (range[i].l > ed) { res++; ed = range[i].r; } } cout << res << endl; return 0; }
