标签: 数组
难度: Medium
Submission
运行时间: 36 ms
内存: 20.2 MB
class Solution:
def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:
ans = []
for i in intervals:
if i[1]<=toBeRemoved[0] or i[0]>=toBeRemoved[1]:
ans.append(i)
elif i[0]<toBeRemoved[0] and i[1]>toBeRemoved[1]:
ans.append([i[0],toBeRemoved[0]])
ans.append([toBeRemoved[1],i[1]])
elif i[0]<toBeRemoved[0] and i[1]<toBeRemoved[1]:
ans.append([i[0],toBeRemoved[0]])
elif i[0]<toBeRemoved[1] and i[1]>toBeRemoved[1]:
ans.append([toBeRemoved[1],i[1]])
elif i[0]==toBeRemoved[0] and i[1]>toBeRemoved[1]:
ans.append(toBeRemoved[1],i[1])
elif i[0]<toBeRemoved[0] and i[1]==toBeRemoved[1]:
ans.append([i[0],toBeRemoved[0]])
return ans
Explain
该题解方法遍历给定的所有区间，针对每个区间根据与toBeRemoved区间的相对位置做不同处理。如果当前区间完全在toBeRemoved区间之前或之后，则当前区间不受影响，直接添加到结果列表。如果当前区间被toBeRemoved区间部分或完全覆盖，则根据覆盖情况划分出不受影响的部分，加入到结果列表。具体处理方式包括：完全不重叠、部分重叠和完全覆盖。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:
ans = [] # 初始化答案列表
for i in intervals: # 遍历每个区间
# 判断区间与toBeRemoved的关系并处理
if i[1] <= toBeRemoved[0] or i[0] >= toBeRemoved[1]:
ans.append(i) # 完全不重叠，直接添加
elif i[0] < toBeRemoved[0] and i[1] > toBeRemoved[1]:
ans.append([i[0], toBeRemoved[0]])
ans.append([toBeRemoved[1], i[1]]) # 被完全覆盖，分割成两部分
elif i[0] < toBeRemoved[0] and i[1] <= toBeRemoved[1]:
ans.append([i[0], toBeRemoved[0]]) # 部分重叠，左侧不被覆盖
elif i[0] < toBeRemoved[1] and i[1] > toBeRemoved[1]:
ans.append([toBeRemoved[1], i[1]]) # 部分重叠，右侧不被覆盖
elif i[0] == toBeRemoved[0] and i[1] > toBeRemoved[1]:
ans.append([toBeRemoved[1], i[1]]) # 起点相同，右侧不被覆盖
elif i[0] < toBeRemoved[0] and i[1] == toBeRemoved[1]:
ans.append([i[0], toBeRemoved[0]]) # 终点相同，左侧不被覆盖
return ans # 返回处理后的区间列表
Explore
在题解中，三种情况是这样判断的：1. 完全不重叠，即当前区间的结束点小于或等于toBeRemoved区间的起始点，或当前区间的起始点大于或等于toBeRemoved区间的结束点。这种情况下，当前区间与toBeRemoved无任何交集。2. 部分重叠，是指当前区间的一部分与toBeRemoved区间重叠，但不是完全覆盖。这种情况具体表现为当前区间的起始点在toBeRemoved起始点之前，但结束点在toBeRemoved区间内；或当前区间的起始点在toBeRemoved区间内，但结束点在toBeRemoved结束点之后。3. 完全覆盖，是指toBeRemoved区间的起始点和结束点都处于当前区间内部，从而toBeRemoved完全覆盖了当前区间的一部分。通过比较区间的起始和结束点可以判断这些情况。
选择将不重叠的部分分割出来而不是修改原区间的值是因为：1. 保持数据不可变性，避免原始数据结构的修改可能带来的错误和复杂性。2. 分割出来的新区间可以直接添加到结果列表中，这样处理更为直接和清晰。3. 修改原区间的值可能会影响到后续的判断和处理逻辑，尤其是在循环中处理多个区间时。因此，从设计和实现的角度考虑，分割出不重叠的部分更为合理且安全。
题解已经涵盖了所有可能的重叠情况，包括完全不重叠、部分重叠的几种情况（左侧或右侧重叠，起点或终点相同），以及完全覆盖的情况。这些基本涵盖了所有与toBeRemoved区间可能的相对位置关系。因此，按照当前的描述和逻辑，不存在题解未涉及到的其他情况。
题解中描述的情况有误，如果一个区间被toBeRemoved区间完全覆盖，实际上应该没有部分被添加到结果列表中。正确的处理应该是：如果toBeRemoved区间完全覆盖了当前区间的一部分（即toBeRemoved区间的起始点和结束点都在当前区间内部），则应分割出不被覆盖的两端。如果toBeRemoved区间完全包括整个当前区间，则不应该添加任何部分到结果列表。因此，如果按照题解原先的描述处理，确实可能导致错误的输出，即错误地将完全被覆盖的区间分割成两个新区间。