[15. Interval consolidation]

Interval merging

subject

Given n Intervals [l_i,r_i] 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
−10⁹≤ l_i ≤ r_i≤10⁹

sample input ：

5
1 2
2 4
5 6
7 8
7 9

sample output ：

3

Code

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

using namespace std;

typedef pair<int, int> PII;

const int N = 100010;

int n;
vector<PII> segs;


void merge(vector<PII> &segs)
{
     
    vector<PII>  res;                  // Save the result of interval merging 
    sort(segs.begin(), segs.end());    // Sort ,pair Sort first sort by left endpoint , Then sort by the right endpoint 

    int st = -2e9, ed = -2e9;           //  When you haven't traversed any interval , First, you can set a boundary value 
    
    for (auto seg : segs)
        if (ed < seg.first)            // Judge whether there is intersection 
        {
     
            if (st != -2e9)  res.push_back({
     st, ed});  // It can't be our initial interval at the beginning , If there is no intersection , Just add it to the answer 
            st = seg.first, ed = seg.second;           // Update interval 
        }
        else 
        {
     
            ed = max(ed, seg.second);                 // At this time, there is intersection , You need to put the right endpoint , Update to the longer value 
             //cout << ed << seg.second <<endl;
        }
           
        
    if (st != -2e9) res.push_back({
     st, ed});           // Add the last interval to the answer . Judgment is mainly to prevent the array we enter , There is no interval , Prevent is empty 
    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);             // Perform interval merging 

  // for (auto ses : segs)
   // {
     
   // cout << ses.first << ses.second << endl;
   // }
    
    cout << segs.size() << endl;
    return 0;
}