AcWing 803. 区间合并-python3实现
原题链接
简单
作者:
机械佬也想学编程
,
2020-06-25 02:02:57
,
所有人可见
,
阅读 477
def merge(segs):
segs.sort() #对序列中的区间进行排序,sort函数默认以区间左端点为key进行排序
res = []
first = True #作为判断第一个区间的标记,方便给start和end赋值
for l, r in segs:
if first:
start, end = l, r
first = False
else:
if l > end: # 第二个区间的左端点大于第一个区间的右端点,不能合并
res.append((start, end)) #将第一个区间添加到res序列中,然后维护下一个区间
start = l
end = r
else: # 第二个区间的左端点小于第一个区间的右端点,可以合并
end = max(r, end) #更新右端点为r和end中的最大值
res.append((start, end)) # 循环结束后将最后一个区间添加到res序列中
return res
n = int(input())
segs = [] #存放所有区间的序列
for _ in range(n):
l, r = map(int, input().split())
segs.append((l,r))
res = merge(segs)
print(len(res))