一：基本思路

sort(segs.begin(), segs.end())根据segs的第一个数进行排序。
区间根据左边界排好序以后，分下面图的三种情况，本质就是两种情况。
image.png

  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  5. using namespace std;
  7. int n;
  8. typedef pair<int, int> PII; //临时存储区间
  9. vector<PII> res, segs; 
  11. void merge(vector<PII> &segs) { //避免拷贝构造函数的执行，占用性能
  12.     sort(segs.begin(), segs.end()); //sort执行的时候根据左边界执行
  13.     int st = -2e9; 
  14.     int ed = -2e9;
  15.     for (auto seg : segs) {
  16.         if (ed < seg.first) { // 图中第三种情况
  17.             if (ed != -2e9) res.push_back({st, ed}); //if的存在是避免初试的st和ed被加入到res中
  18.             st = seg.first;
  19.             ed = seg.second;
  20.         } else {
  21.             ed = max(ed, seg.second);
  22.         }
  23.     }
  24.     if (st != -2e9) res.push_back({st, ed}); // 正常情况下，最后一定是有一个区间的
  25.     segs = res;
  26. }
  27. int main() 
  28. {
  29.     cin >> n;
  30.     for (int i = 0; i < n; i++) 
  31.     {
  32.         int l, r;
  33.         cin >> l >> r;
  34.         segs.push_back({l, r});
  35.     }
  36.     merge(segs);
  37.     cout << segs.size() << endl;
  38.     return 0;
  39. }