AcWing刷题-区间合并

校门外的树

区间合并：

from typing import List
def merge(intervals: List[List[int]]) -> List[List[int]]:
    # 按照第一个元素从小到大进行排序
    intervals.sort(key=lambda x: x[0])
    # 初始化一个新的数组
    new_list = list()
    for i in intervals:
        # 把第一个数组元素添加到新的数组
        if not new_list:
            new_list.append(i)
            continue
        # 如果有重合 就合并
        if new_list[-1][1] >= i[0]:
            x = max(new_list[-1][1], i[1])
            new_list[-1][1] = max(new_list[-1][1], i[1])
        # 如果没有重合 就直接添加到新的数组
        else:
            new_list.append(i)
    return new_list
L,M = map(int,input().split())
a = []
for _ in range(M):
    a.append(list(map(int,input().split())))
new_a = merge(a)
sum = 0
for elem in new_a:
    sum += elem[1]-elem[0]+1
print(L+1-sum)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28