区间合并题

步骤：

1.按区间左端点排序

2.比较当前区间的右端点与下一区间的左端点

3.包含关系，有交集，没交集；

给定 nn 个区间 [li,ri][li,ri]，要求合并所有有交集的区间。

注意如果在端点处相交，也算有交集。

输出合并完成后的区间个数。

例如：[1,3][1,3] 和 [2,6][2,6] 可以合并为一个区间 [1,6][1,6]。

输入格式

第一行包含整数 nn。

接下来 nn 行，每行包含两个整数 ll 和 rr。

输出格式

共一行，包含一个整数，表示合并区间完成后的区间个数。

数据范围

1≤n≤1000001≤n≤100000,
−109≤li≤ri≤109−109≤li≤ri≤109

输入样例：

5
1 2
2 4
5 6
7 8
7 9

输出样例：

3

#include
#include
#include

using namespace std;
    
typedef pair PII;

vectorsegs;

int  merge (vector &segs)
{
    
    sort(segs.begin() ,segs.end());//系统优先按first排序，再以second排序
    int st = -2e9,ed = -2e9,num = 0;
    for (auto seg : segs)
        if(ed < seg.first)
        {
            if(st != -2e9 ) num ++;//加的是前一个即刚更新的ed的那个区间，，，因为经过循环的判断后才能确定最终区间的右端点
            st = seg.first,ed = seg.second ;
        }
        else ed = max(ed, seg.second);
        
    if( st != -2e9) num ++;//判断条件是为了防止是segs空区间，加的是最后一个区间（前面循环将其更新后循环结束，由于是最后一个区间
    //所以未进行右端点判断，所以在循环结束后加上。
    
    return num;
}

int main()
{
    int n;
    cin>>n;
   while (n --)
   {
       int l ,r;
       cin >> l >> r;
       segs.push_back({l, r});
   }
   
   
   cout << merge (segs) << endl;

    return 0;
}