题目描述

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

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

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

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

输入格式
第一行包含整数n。

接下来n行，每行包含两个整数 l 和 r。

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

数据范围
1≤n≤100000,
−10^9≤li≤ri≤10^9

样例

输入样例：
5
1 2
2 4
5 6
7 8
7 9
输出样例：
3

算法1

区间合并

1.按区间左端点排序
2.扫描所有区间，把所有有交集的区间合并

python 代码

def merge(seg):
    res = 0
    seg.sort(key=lambda x: x[0])
    st = -2e9
    ed = -2e9
    for i in range(len(seg)):
        if ed<seg[i][0]:        #无交集
            if st!=-2e9:
                res+=1
            st = seg[i][0]
            ed = seg[i][1]
        else:                   #有交集
            ed = max(ed,seg[i][1])
    if st != -2e9:      #防止空区间
        res+=1          #将最后的区间加入到答案中
    return res


if __name__ == "__main__":
    s = []
    n = int(input())
    for i in range(n):
        l, r = map(int, input().split())
        s.append((l, r))
    print(merge(s))