算法1

利用贪心算法快速合并空间

时间复杂度

O（n）

python 代码

#边合并边计数

if __name__=="__main__":
    n = int(input())
    count = 1 if n > 0 else 0
    Interval = []
    for _ in range(n):
        Interval.append([int(i) for i in input().split()])
    Interval.sort()
    for i in range(1,n):
        if Interval[i][0]>Interval[i-1][1]:
            count += 1
        else:
            Interval[i][1]=max(Interval[i][1],Interval[i-1][1])
            Interval[i][0]=min(Interval[i][0],Interval[i-1][0])
    print(count)