文章目录[隐藏]
You are given two lists of closed intervals, firstList and secondList, where firstList[i] = [starti, endi] and secondList[j] = [startj, endj]. Each list of intervals is pairwise disjoint and in sorted order.
Return the intersection of these two interval lists.
A closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b.
The intersection of two closed intervals is a set of real numbers that are either empty or represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3].
- [Interval List Intersections](Interval List Intersections)
Solution
- submit code
class Solution:
def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:
intput = firstList + secondList
# 先index0排序
intput.sort(key=lambda x: x[0])
# indexo相同时，index1降序
for x in range(len(intput) - 1):
if intput[x][0] == intput[x+1][0] and intput[x][1] < intput[x+1][1]:
intput[x][1],intput[x+1][1] = intput[x+1][1],intput[x][1]
# base case
if len(intput) == 1:
return intput
left = intput[0][0]
right = intput[0][1]
ret = []
for x in range(1,len(intput)):
# 部分重叠时
# little overlap
if intput[x][0] <= right and intput[x][1] >= left and intput[x][1] >= right:
ret.append([intput[x][0],right])
left = right
right = intput[x][1]
# 覆盖时
# cover
elif intput[x][0] >= left and intput[x][1] <= right:
ret.append([intput[x][0],intput[x][1]])
left = intput[x][0]
# 没有重叠时
# no overlap
elif intput[x][0] > right:
left = intput[x][0]
right = intput[x][1]
return ret
- full code
class Solution:
def intervalIntersection(self, firstList, secondList):
intput = firstList + secondList
# 先index0排序
intput.sort(key=lambda x: x[0])
# indexo相同时，index1降序
for x in range(len(intput) - 1):
if intput[x][0] == intput[x+1][0] and intput[x][1] < intput[x+1][1]:
intput[x][1],intput[x+1][1] = intput[x+1][1],intput[x][1]
print(intput)
# base case
if len(intput) == 1:
return intput
left = intput[0][0]
right = intput[0][1]
ret = []
for x in range(1,len(intput)):
print("x:",x,"left:",left,"right:",right,"intput[x][0]:",intput[x][0],"intput[x][1]:",intput[x][1])
# 部分重叠时
# little overlap
if intput[x][0] <= right and intput[x][1] >= left and intput[x][1] >= right:
ret.append([intput[x][0],right])
left = right
right = intput[x][1]
# 覆盖时
# cover
elif intput[x][0] >= left and intput[x][1] <= right:
ret.append([intput[x][0],intput[x][1]])
left = intput[x][0]
# 没有重叠时
# no overlap
elif intput[x][0] > right:
left = intput[x][0]
right = intput[x][1]
return ret
S = Solution()
firstList = [[0,2],[5,10],[13,23],[24,25]]
secondList = [[1,5],[8,9],[15,24],[24,28]]
print(S.intervalIntersection(firstList,secondList))
