题目描述

区间和 C++版本

样例

// 区间和
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int, int> PII;
vector<PII> segs;

vector<PII> merge_all(vector<PII> &segs)
{
    vector<PII> ans;
    // 按照第一位进行升序排列
    sort(segs.begin(),segs.end());
    int l = -2e9, r = -2e9;
    int k = 0;
    for(auto seg:segs)
    {
        if (r < seg.first)
        {
            // 非首次添加，记录添加数组
            if(l != -2e9) ans.push_back({ l,r });
            // 首次添加
            l = seg.first, r = seg.second;
        }
        else
        {
            // 更新右端点
            r = max(r, seg.second);
        }
    }
    if(l != -2e9) ans.push_back({ l,r });
    return ans;
}


int main()
{
    int n,l,r;
    cin >> n;

    while (n-- > 0)
    {
        cin >> l >> r;
        segs.push_back({l,r});
    }

    vector<PII> ans = merge_all(segs);
    cout << ans.size() << endl;

    return 0;
}