Leetcode练习(Python)：数组类：第57题：给出一个无重叠的 ，按照区间起始端点排序的区间列表。 在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合
标签：new 简单 bsp als data iar python append sel
题目：
给出一个无重叠的 ，按照区间起始端点排序的区间列表。
在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
思路：开始使用纯逻辑的思路，使用了大量的判断，如程序2所示，可以通过题目的两个例子，但是在自创例子时出现了超时的提示(要把复杂的问题简单化）。看了一个大神的程序，然后模仿了下来，如程序1，写的很精巧。
程序1：
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
intervals.sort(key = lambda data : data[0])
length = len(intervals)
index = 0
auxiliary_index = 0
while index
if newInterval[1]
break
elif newInterval[0] > intervals[index][1]:
pass
else:
newInterval[0] = min(newInterval[0], intervals[index][0])
newInterval[1] = max(newInterval[1], intervals[index][1])
auxiliary_index += 1
index += 1
if auxiliary_index > 0:
intervals = intervals[: index - auxiliary_index] + intervals[index :]
intervals.insert(index - auxiliary_index, newInterval)
return intervals
程序2：
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
intervals.sort(key = lambda data : data[0])
length = len(intervals)
if length
return [newInterval]
if length == 1:
if intervals[0][1] >= newInterval[0] and intervals[0][1]
temp = []
left = min(intervals[0][0], newInterval[0])
temp.append(left)
right = max(intervals[0][1], newInterval[1])
temp.append(right)
return [temp]
elif intervals[0][1]
temp_1 = []
left = intervals[0][0]
temp_1.append(left)
right = intervals[0][1]
temp_1.append(right)
temp_2 = []
left = newInterval[0]
temp_2.append(left)
right = newInterval[1]
temp_2.append(right)
result = []
result.append(temp_1)
result.append(temp_2)
return result
elif intervals[0][0] > newInterval[1]:
temp_3 = []
left = newInterval[0]
temp_3.append(left)
right = newInterval[1]
temp_3.append(right)
temp_4 = []
left = intervals[0][0]
temp_4.append(left)
right = intervals[0][1]
temp_4.append(right)
result_1 = []
result_1.append(temp_3)
result_1.append(temp_4)
return result_1
elif intervals[0][0] >= newInterval[0] and intervals[0][1] > newInterval[1]:
temp_5 = []
left = min(intervals[0][0], newInterval[0])
temp_5.append(left)
right = max(intervals[0][1], newInterval[1])
temp_5.append(right)
return [temp_5]
index = 1
while index
if newInterval[0] >= intervals[index - 1][0] and newInterval[0]
if newInterval[1] >= intervals[index - 1][1] and newInterval[1]
intervals[index - 1][0] = intervals[index - 1][0]
intervals[index - 1][1] = newInterval[1]
elif newInterval[1]
intervals[index - 1][0] = intervals[index - 1][0]
intervals[index - 1][1] = intervals[index - 1][1]
elif intervals[index][0]
intervals[index - 1][0] = intervals[index - 1][0]
intervals[index - 1][1] = intervals[index][1]
elif newInterval[1] >= intervals[index][1]:
del intervals[index]
intervals[index - 1][0] = intervals[index - 1][0]
intervals[index - 1][1] = newInterval[1]
#del intervals[index]
elif newInterval[0] > intervals[index - 1][0] and newInterval[0]
if newInterval[1] >= intervals[index - 1][1] and newInterval[1]
intervals[index - 1][0] = intervals[index - 1][0]
intervals[index - 1][1] = newInterval[1]
elif newInterval[1]
intervals[index - 1][0] = intervals[index - 1][0]
intervals[index - 1][1] = intervals[index - 1][1]
elif intervals[index][0]
intervals[index - 1][0] = intervals[index - 1][0]
intervals[index - 1][1] = intervals[index][1]
elif newInterval[1] >= intervals[index][1]:
del intervals[index]
intervals[index - 1][0] = intervals[index - 1][0]
intervals[index - 1][1] = newInterval[1]
elif newInterval[1]
intervals.insert(index - 1, newInterval)
elif newInterval[0] > intervals[index - 1][1]:
if newInterval[1]
intervals.insert(index, newInterval)
elif newInterval[1] >= intervals[index][0] and newInterval[1]
#del intervals[index]
intervals[index][0] = intervals[index][0]
intervals[index][1] = newInterval[1]
elif newInterval[1] >= intervals[index][0] and newInterval[1] >= intervals[index][1]:
#del intervals[index]
intervals[index][0] = intervals[index][0]
intervals[index][1] = newInterval[1]
elif newInterval[0]
if newInterval[1]
intervals[index - 1][0] = newInterval[0]
intervals[index - 1][1] = intervals[index - 1][1]
elif newInterval[1] > intervals[index - 1][1] and newInterval[1]
intervals[index - 1][0] = newInterval[0]
intervals[index - 1][1] = intervals[index - 1][1]
elif newInterval[1] > intervals[index - 1][1] and newInterval[1] >= intervals[index][0]:
if newInterval[1]
intervals[index - 1][0] = newInterval[0]
intervals[index - 1][1] = intervals[index][1]
else:
intervals[index - 1][0] = newInterval[0]
intervals[index - 1][1] = newInterval[1]
index += 1
index_1 = 1
while index_1
if intervals[index_1][0]
intervals[index_1 - 1][1] = max(intervals[index_1 - 1][1], intervals[index_1][1])
del intervals[index_1]
else:
index_1 += 1
return intervals
Leetcode练习(Python)：数组类：第57题：给出一个无重叠的 ，按照区间起始端点排序的区间列表。 在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
标签：new 简单 bsp als data iar python append sel
原文地址：https://www.cnblogs.com/zhuozige/p/12740361.html
评论