【贪心】洛谷 P1803 凌乱的yyy / 线段覆盖
P1803 凌乱的yyy / 线段覆盖
文章目录
- 题目背景
- 题目描述
- 输入格式:
- 输出格式:
- 数据范围
- 输入样例
- 输出样例
- 方法:贪心
- 解题思路
- 代码
- 复杂度分析:
题目背景
快 noip 了,yyy 很紧张!
题目描述
现在各大 oj 上有 n 个比赛,每个比赛的开始、结束的时间点是知道的。
yyy 认为,参加越多的比赛,noip 就能考的越好(假的)。
所以,他想知道他最多能参加几个比赛。
由于 yyy 是蒟蒻,如果要参加一个比赛必须善始善终,而且不能同时参加 2 个及以上的比赛。
输入格式:
第一行是一个整数 n ,接下来 n 行每行是 2 个整数 a i , b i ( a i < b i ) a_{i},b_{i} ( a_{i}<b_{i} ) ai,bi(ai<bi),表示比赛开始、结束的时间。
输出格式:
一个整数最多参加的比赛数目。
数据范围
- 1 ≤ n ≤ 2 × 1 0 4 1≤n≤2\times10^4 1≤n≤2×104
- − 2 31 ≤ a ≤ b < 2 31 -2^{31} \leq a \leq b \lt 2^{31} −231≤a≤b<231
输入样例
3
0 2
2 4
1 3
输出样例
2
方法:贪心
解题思路
本题和 908. 最大不相交区间数量 的解题思路是一样的。
唯一的变化是,线段覆盖的相交是不包括两个不同区间的左右端点相重合的。
代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1000010;
struct Range {
int l, r;
bool operator < (const Range& W) const {
return r < W.r;
}
} range[N];
int n;
int main() {
cin >> n;
for(int i = 0; i < n; i++) {
int l, r;
cin >> l >> r;
range[i] = {l, r};
}
sort(range, range + n);
int res = 0, ed = -2e9;
for(int i = 0; i < n; i++)
if(ed <= range[i].l) {
res++;
ed = range[i].r;
}
cout << res;
return 0;
}
复杂度分析:
- 时间复杂度: O ( n × l o g 2 n ) O(n\times log_2n) O(n×log2n)
- 空间复杂度: O ( n ) O(n) O(n)