在Python中查找不与剪切区间相交的区间的程序
假设我们有一个排序且不相交的区间列表和另一个表示区间的列表剪切。我们必须删除所有与切割区间相交的区间部分,并返回新的列表。
因此,如果输入为intervals = [[2, 11],[13, 31],[41, 61]] cut = [8, 46],那么输出将为[[2, 8],[46, 61]]
要解决此问题,我们将遵循以下步骤-
- cut_start,cut_end:= cut
- ans:=新列表
- 对于每个start,end中的间隔,执行以下操作-
- 如果cut_start和start的最大值和cut_end和end的最小值,那么
- 如果start小于cut_start,则
- 将间隔[start,cut_start]插入ans
- 如果end> cut_end,则
- 将间隔[cut_end,end]插入ans
- 否则,
- 如果cut_start和start的最大值和cut_end和end的最小值,那么
- 返回ans
让我们看以下实现以更好地理解-
示例
class Solution:
def solve(self, intervals, cut):
cut_start, cut_end = cut
ans = []
for start,end in intervals:
if max(cut_start, start) < min(end, cut_end):
if start < cut_start:
ans.append([start, cut_start])
if end > cut_end:
ans.append([cut_end, end])
else:
ans.append([start, end])
return ans
ob = Solution()
intervals = [[2,11],[13,31],[41,61]] cut = [8,46]
print(ob.solve(intervals, cut))
输入
[[2, 11],[13, 31],[41, 61]],[8, 46]
输出
[[2, 8],[46, 61]]