51Nod-2071 不相交子区间 题解

不相交子区间

题目概述

从给出的线段中去掉尽量少的线段，使得剩下的线段两两之间没有内部公共点，求最后剩下几条线段

思路分析

按照右端点排序，记录当前能到达的最远右端点

对于每条线段，如果左端点在最远右端点左边，则说明该线段需要被删掉

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long llong;
const int N = 2e5 + 5;
const int MOD = 1e9 + 7;
llong n;
struct Node {
    int l, r;
    Node(int l = 0, int r = 0) : l(l), r(r) { }
    bool operator < (Node ano) {
        return r < ano.r;
    }
};

vector<Node> v;

int main() {
    #ifdef LOCAL
        freopen("D:/Code/ACM/in.in", "r", stdin);
        freopen("D:/Code/ACM/out.out", "w", stdout);
    #endif
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        if (l > r)  swap(l ,r);
        v.emplace_back(Node(l, r));
    }
    sort(v.begin(), v.end());
    int r = -1000, ans = n;
    for (int i = 0; i < n; i++) {
        if (v[i].l < r) {
            ans--;
        } else {
            r = max(r, v[i].r);
        }
    }
    cout << ans << "\n";
    return 0;
}