区间合并
作者:
成理第一深情
,
2024-01-06 11:39:47
,
所有人可见
,
阅读 69
Acwing 803.区间合并
- 先按照每个区间左端点升序排序
- 三种情况,包含,相交,不相交分别分析
- 包含:区间st和ed不变
- 相交:ed变大
- 不相交:res+=1,st和ed更新为不相交的那个区间的st和ed
def merge(segs):
res = [] # 合并后的区间
segs = sorted(segs, lambda x: x[0])
# print(segs)
st, ed = -2e9, -2e9
for l, r in segs:
if ed < l: # 如果当前维护的区间和下一个区间不相交,就把当前的维护的区间加入答案,并更新当前维护的区间
if st != -2e9:
res.append((st, ed))
st, ed = l, r
else: # 否则,如果相交,看谁右端点大
ed = max(ed, r)
if st != -2e9: # 剩下最后一个区间要加到答案里,这个判断条件是为了防止输入为空
res.append((st, ed))
return res
if __name__ == "__main__":
segs = []
n = int(input())
for i in range(n):
l, r = map(int, input().split(' '))
segs.append((l, r))
# print(segs)
res = merge(segs)
print(len(res))
注意点
- 在 Python 中,当函数参数是一个可变对象(如列表、字典、集合等)时,对该参数的任何修改都会影响到原始对象。这是因为在 Python 中,变量实际上是对对象的引用。当你在函数内部对传入的参数进行修改时,你实际上是在修改这个引用所指向的对象
- 传递方式:当 segs 作为参数传递给 merge 函数时,你实际上传递的是对原始列表的引用,而不是其副本。这意味着在函数内部对segs的任何修改都会反映到传入的原始列表上,除非你明确地创建了一个副本。
def merge(segs):
segs = sorted(segs, key=lambda x: x[0]) # 创建一个新的排序后的列表
- 上面的方式是得到了sorted(segs)得到了segs排序后的副本,原来的segs不变
- 同时segs = sorted(…)赋值给了新的列表对象segs,这只是函数内的segs,而不是外的segs,所以在函数外部,segs任然指向了原始的未排序的列表