acwing 803. Interval merging

Given n Intervals [li,ri], It is required to merge all intersecting intervals .
Note that if you intersect at the end , There is also an intersection .
Output the number of intervals after merging .

for example ：[1,3] and [2,6] Can be merged into one interval [1,6].

Input format
The first line contains integers n.

Next n That's ok , Each line contains two integers l and r.

Output format
All in one line , Contains an integer , Indicates the number of intervals after the consolidation interval is completed .

Data range
1≤n≤100000,
−109≤li≤ri≤109
sample input ：
5
1 2
2 4
5 6
7 8
7 9
sample output ：
3

Topic diagram ： Here, the same endpoint can be merged

Question making steps ：

1. Sort according to the left end point of the interval
2. When an interval is a blue line , Only green will appear in the subsequent interval 3 In this case , The red condition will not occur
   
3. In the first case, there is no need to update the interval , The second case will extend the previous interval , After the third situation occurs , The previously maintained interval will be saved , In the latter case, the current interval is maintained （ The maintenance interval is updated to the third case ）.

#include<iostream>
#include<vector>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 100010;

int n;
vector<PII> segs;


void merge(vector<PII>& segs)
{
    
    vector<PII> re;
    sort(segs.begin(), segs.end());  // c++ Chinese vs pair  Sort first sort by left endpoint 
    
    int st = -2e9, ed = -2e9;
    for(auto seg : segs)
        if(ed < seg.first)  //  The third case 
        {
    
            if(st != -2e9) re.push_back({
    st, ed});
            st =seg.first, ed = seg.second;  //  Update maintenance interval 
        }
        else ed = max(ed, seg.second); //  First of all 、 II. Two cases 
    
    //if(st != -2e9) //  It seems that you can do it without this AC
        re.push_back({
    st,ed});  //  Submit the last interval 
    
    segs = re;
}

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;
}