区间合并的目的:将一些有交集的区间合并成没有交集的区间;
具体思路:
- 按照区间左端点排序;(不要忘记)
- 维护一个当前区间,通过比较维护区间结尾和输入区间开头来确定是否存在新的交集:
2.1 若无重叠部分==》保存当前结果,并创建新区间;
2.2 若有重叠部分==》更新当前区间;
注意最后一个区间在循环内不会被加入res,要单独保存!
# 读取区间数
n = int(input())
# 读取所有区间
sec = []
for i in range(n):
l, r = map(int, input().split())
sec.append([l, r])
# 按照左端点排序
sec.sort()
# 合并区间
res = []
l = -1
r = -1
for item in sec:
if item[0] > r:
if r != -1:
res.append([l, r])
l = item[0]
r = item[1]
else:
r = max(r, item[1])
res.append([l, r])
print(len(res))