【贪心】洛谷 P1803 凌乱的yyy / 线段覆盖

题目背景

快 noip 了yyy 很紧张

题目描述

现在各大 oj 上有 n 个比赛每个比赛的开始、结束的时间点是知道的。

yyy 认为参加越多的比赛noip 就能考的越好假的。

所以他想知道他最多能参加几个比赛。

由于 yyy 是蒟蒻如果要参加一个比赛必须善始善终而且不能同时参加 2 个及以上的比赛。

输入格式

第一行是一个整数 n 接下来 n 行每行是 2 个整数 $a_i,b_i(a_i<b_i)$表示比赛开始、结束的时间。

输出格式

一个整数最多参加的比赛数目。

数据范围

• $1\le n\le 2\times 10^4$
• $-2^{31}\le a\le b<2^{31}$

输入样例

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\times lo{g}_{2}n)$
• 空间复杂度$O(n)$