19.区间合并

解题思路：

1：按区间左端点从小到大排序

2：遍历一遍。遍历的同时维护一个区间。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef pair<int, int> PII;
 4 void merge(vector<PII> &segs) {
 5     vector<PII> res;
 6     sort(segs.begin(), segs.end());
 7     //优先以左端点排序，再以右端点排序 
 8     int st = -2e9, ed = -2e9; //设置一个边界值 
 9     for (int i = 0; i < segs.size(); i++) { //扫描所有区间 
10         if (ed < segs[i].first) {
11             if (st != -2e9) {
12                 res.push_back({st, ed}); //找到了一个区间 
13             }
14             st = segs[i].first;
15             ed = segs[i].second;
16         } else {
17             ed = max(ed, segs[i].second);
18         }
19     }
20     if (st != -2e9) { //防止输入里没有任何区间 
21         res.push_back({st, ed});
22     }
23     segs = res;
24 }
25 int main() {
26     vector<PII> segs;
27     int n;
28     cin >> n;
29     for (int i = 0; i < n; i++) {
30         int l, r;
31         cin >> l >> r;
32         segs.push_back({l, r});
33     }
34     merge(segs);
35     cout << segs.size() << endl;
36     return 0;
37 }