区间和并

题目分析：

用 pair 存放区间。first 代表左端点，second 右端点。
先要对pair 排序，因为从做到右一次判断每个区间的交集。用start ，end 表示能够合并的区间端点。
如果end < pair.first 表示当前的区间和后面一个区间没有交点，可以存放。

样例分析：

1 2 3 4 5 6 7 8 9 
输入样例：
5
1 2
2 4
5 6
7 8
7 9

核心思想：

循环每个区间，如果这个区间和上一个区间(start,end)没有交集，把上一个区间插进去。再把更新成这个区间更新成start，end；
如果有交集，更新最远的end，不用插进去，直接循环下一次。

核心代码：

if(end < pair.first) 
{
    if(start != INT_MIN) another_pair.push_back({start, end});
    //换成下一个区间 
    start = pair.first; end = pair.second;
}else
{
    // 如果可以合并，就合并成最长区间
    end = max(end, pair.second);
}
//最后一个区间也加进去
if(start != INT_MIN) another_pair.push_back({start, end});
//最后another_pair存放的就是合并后的区间。

样例

5
1 2
2 4
5 6
7 8
7 9

算法1

$O(n)$

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int, int>PII;
vector<PII> res;

void merge(vector<PII> &res){
    sort(res.begin(), res.end());
    int start = -1e9, end = -1e9; vector<PII> tmp;
    for(auto item : res){
        if(end < item.first)
        {
            if(start != -1e9)tmp.push_back({start, end});
            start = item.first; end = item.second;
        }else
            end = max(end, item.second);
    }
    if(start != -1e9)tmp.push_back({start, end});
    res = tmp;
}
int main(){
    int n; cin >> n;
    while(n--){
        int l, r;
        cin >> l >> r;
        res.push_back({l ,r});

    }
    merge(res);
     cout << res.size();
    //  for(int i = 0; i< res.size(); ++i)cout << res[1].first << " " << res[i].second << endl;
    return 0;
}