CMB26 挑选代表

描述

我们有很多区域，每个区域都是从a到b的闭区间，现在我们要从每个区间中挑选至少2个数，那么最少挑选多少个？

输入描述：

第一行是N（N<10000）,表示有N个区间，之间可以重复然后每一行是ai,bi，持续N行，表示现在区间。均小于100000

输出描述：

输出一个数，代表最少选取数量。

示例1

输入：

4 4 7 2 4 0 2 3 6

输出：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main(){
    int n; cin>>n;
    vector<vector<int>> a;
    for(int i=0; i<n; i++) {
        int x , y;
        cin >> x >> y;
        vector<int> tmp{x,y};
        a.emplace_back(tmp);
    }
    sort(a.begin(), a.end(), [](const auto &u, const auto &v){
        return u[1] < v[1];
    });
    int out = 2;
    int m = a.size();
    int l = a[0][0], r=a[0][1];
    for(int i = 1; i<m;i++){
        if(a[i][0] == r){
            out = out + 1;
            r = a[i][1];
        }else if(a[i][0] > r){
            out = out +2;
            l = a[i][0];
            r = a[i][1];
        }
    }
    cout << out << endl;
    return 0;
}