5.12

区间合并问题：

• 题目描述：给出n段区间，如果区间内,l -r存在交集，那么就可以合并，需要更新区间，如果不存在交集，那么就直接将单独的区间个数++，最后返回区间合并后的区间个数

• 

   

   

• 解题思路：

  • 将区间通过pair进行归类，并排序(可以去除包含的区间，并且可以从小到大排序也方便进行插入，计数)；

  • 找到没有交集的前后区间，进行计数；

  • 找到有交集的区间，进行更换区间；

  • #include iostream #include algorithm #include vector  using namespace std;  typedef pair<int, int> pii; vector<pii> segs; int n;  void merge(vector<pii> &segs) {     sort(segs.begin(), segs.end());     //排序后可以将本来是完全子区间的直接去重掉，sort对于pair排序的话，是先对前面进行排序，然后再对后排     vector<pii> res;     int st = -2e9, ed = -2e9;     //将一开始的左边和右边都置为负无穷     for (auto seg: segs) {         //对所有segs里面的值进行遍历         if (ed < seg.first) {             //如果是两条线段的话，原来线段的末尾<后面一条线段的最开始，那么就是需要进行计数加加的时候；             if (st != -2e9)                 //如果不是第一次的话 ，就直接加上计数                 res.push_back({st, ed});             st = seg.first, ed = seg.second;//这里才是第一次的初始化。         } else ed = max(ed, seg.second);//否则就需要更新区间     }     if (st != -2e9)         //判断是不是原来的segs是不是空的，如果是空的就不加入，如果不是空的，就加入原来segs的最后一个         res.push_back({st, ed});     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();     return 0; }