AcWing 803. 区间合并-python
原题链接
简单
作者:
Actor丶
,
2020-03-14 20:13:33
,
所有人可见
,
阅读 844
"""
基本思想:按区间的左端点排序,维护一个集合[start,end],逐个读入小区间然后更新维护的集合
区间合并模板:
def merge(segs):
# segs的元素是小区间的左右边界值
res = []
segs.sort() # !!!出错:忘记在区间合并前要按区间的左端点排序了
start = float("-inf"); end = float("-inf") # 初始化要维护的集合的边界[start, end]
for l, r in segs:
if end<l:
if start!=float("-inf"): res.append((start, end))
start = l; end = r
else:
end = max(end, r)
if start!=float("-inf"): res.append((start, end))
return res
"""
def merge(segs):
res = []
segs.sort() # !!!出错:忘记在区间合并前要按区间的左端点排序了
start = float("-inf"); end = float("-inf") # 初始化要维护的集合的边界[start, end]
for l, r in segs:
if end<l:
if start!=float("-inf"): res.append((start, end))
start = l; end = r
else:
end = max(end, r)
if start!=float("-inf"): res.append((start, end))
return res
if __name__=="__main__":
n = int(input().strip())
segs = []
for i in range(n):
l, r = map(int, input().split())
segs.append((l, r))
res = merge(segs)
print(len(res))
感谢