线段

一本通·提高篇 · 代码 · cpp · 难度 3/5 · 共 780 字

按右端点排序贪心选最多不相交线段

一本通
练习

正文

// 原题：https://oj.yecheng.tv/p/T1429
// 题意：数轴上 n 条线段，求最多能选出多少条两两没有重合部分的线段。
// 思路：与活动安排完全相同，按右端点升序排序后贪心。
// 1. 右端点越小，留给右边的空间越大。
// 2. 只要左端点不小于上一条选中线段的右端点，就选它。
// 复杂度：O(n log n) 时间 / O(n) 空间
// 易错点：端点相接（一条的右端点等于另一条的左端点）不算重合，用 >= 判断。
// 易错点：线段端点可能达到 1e6 且 n 高达 1e6，排序要一次读入后再排，不要边读边扫。
#include <bits/stdc++.h>
using namespace std;
struct Seg {
    int l, r;
};
int main(){
    int n;
    if(!(cin >> n)) return 0;
    vector<Seg> a(n);
    for(int i = 0; i < n; i++) cin >> a[i].l >> a[i].r;
    sort(a.begin(), a.end(), [](const Seg& x, const Seg& y){
        return x.r < y.r;
    });
    int ans = 0;
    int last = 0;
    for(int i = 0; i < n; i++){
        if(a[i].l >= last){
            ans++;
            last = a[i].r;
        }
    }
    cout << ans << "\n";
    return 0;
}

线段

正文

一本通·提高篇的其它内容