区间合并

区间合并

用例演示

  • 多个蓝色小区间可以合并为三个绿色区间

解题思路

  • 情况1:无需改变当前区间
  • 情况2:将当前区间的end向后延伸
  • 情况3:当前区间的任务已经完成,可以将当前区间放入答案集中,并将原区间startend更新为粉色区间的startend

实现代码

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;

const int N = 1e5 + 100;

int n;
vector<PII> segs;

void merge(vector<PII> &segs){
    vector<PII> res;


    sort(segs.begin(), segs.end());

    int start = -2e9, end = -2e9;
    // 注意这里end也是-2e9,因为是从左边来的,不能是2e9,否则就比不了啦!
    for(auto seg: segs){
        if(end < seg.first){
            if(start != -2e9){
                res.push_back({start, end});
            }
            start = seg.first, end= seg.second;

        }else{
            end = max(end, seg.second);
        }
    }

    // 将最后一段合并区间也放入答案中
    if(start != -2e9)
        res.push_back({start, end});

    segs = res;
}

int main(){
    cin >> n;

    for(int i = 0; i < n; i ++){
        int l, r;
        cin >> l >> r;

        segs.push_back({l, r});
    }

    merge(segs);

    cout << segs.size() << endl;

    return 0;

}



Enjoy Reading This Article?

Here are some more articles you might like to read next:

  • Google Gemini updates: Flash 1.5, Gemma 2 and Project Astra
  • Displaying External Posts on Your al-folio Blog
  • 强化学习导论
  • 企业项目实训
  • 面试总结