题目描述
给定N个闭区间[ai,bi],请你在数轴上选择尽量少的点,使得每个区间内至少包含一个选出的点。
输出选择的点的最小数量。
位于区间端点上的点也算作区间内。
样例
3
-1 1
2 4
3 5
2
解法思路
贪心
也是先按右端点排序,再从左至右扫一遍并处理一下即可
时间复杂度
排序 $O(nlog_2n)$,处理 $O(n)$,总计 $O(nlog_2n)$
C++ 代码
很好写,一遍 debug 都没有就通过了.
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
struct Segment {
int l, r;
inline friend bool operator < (const Segment &a, const Segment &b) {
return a.r < b.r;
}
} a[N];
int n;
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i].l >> a[i].r;
}
sort(a + 1, a + n + 1);
int answer = n, lastr = a[1].l - 1;
for (int i = 1; i <= n; ++i) {
if (a[i].l <= lastr) --answer;
else lastr = a[i].r;
}
printf("%d\n", answer);
return 0;
}