注意要点,i,j的取值范围很大,如果用set(list(range(i, j+1)))的方式真实还原区间的话,会导致区间搜索超时。
因此,需要根据i, j的本体大小判断两个相邻区间的交并关系。
此外,最后一个区间维护结束后是不会上传到res的,因此res初始值为1。
N = int(input())
qujian_list = []
for i in range(N):
qujian_list.append(list(map(int, input().split())))
def diagnose(list_1, list_2): # list根据区间左端点排序
if list_1[-1] < list_2[0]:
return 'not inter'
if list_1[-1] >= list_2[-1]:
return 'contained'
if list_1[-1] >= list_2[0]:
return 'inter'
qujian_list.sort()
new_list = qujian_list[0]
res = 1
for i in qujian_list[1:]:
if diagnose(new_list, i) == 'not inter':
res += 1
new_list = i
if diagnose(new_list, i) == 'contain':
pass
if diagnose(new_list, i) == 'inter':
new_list = [new_list[0], i[-1]]
print(res)
这个sort没有给cmp_to_key传参啊,怎么就默认了List[0]?
python的 list.sort() 默认用元素的第一个元素排序的