Interval List Intersections

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))
``````

### 要不赞赏一下?

 微信 支付宝 PayPal Bitcoin

``https://www.emperinter.info/2022/04/11/interval-list-intersections/``

 阿里云国际版 20美元 Vultr 10美元 搬瓦工 | Bandwagon 应该有折扣吧？ Just My Socks JMS9272283 【注意手动复制去跳转】 域名 | namesilo `emperinter`(1美元) 币安 币安