题目
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]
.
Example 1:
Input: firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
Example 2:
Input: firstList = [[1,3],[5,9]], secondList = []
Output: []
Constraints:
0 <= firstList.length, secondList.length <= 1000
firstList.length + secondList.length >= 1
0 <= starti < endi <= 109
endi < starti+1
0 <= startj < endj <= 109
endj < startj+1
思路
歪门邪道法:将两个数组合成一个新数组nums并以第一个元素从小到大排序,遍历排序后数组,与此同时记录第二个元素的最大值maxn,当当前第一个元素小于等于maxn时,则表示有重合项,且重合的右边界为min(maxn, nums[i][1])
,此时将重合项保存下来,遍历后所有重合项的数组即为结果。
双指针法:双指针分别表示firstList和secondList的索引,建立循环:判断双指针所在区块是否有重合,如果重合则保存结果;随后根据右边界的大小判断移动哪一个指针。直至指针到达数组边界,返回所有保存的结果。
代码
python版本:
class Solution:
def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:
nums = firstList+secondList
nums.sort(key=lambda num: num[0])
res = []
# print(nums)
maxn = nums[0][1]
for i in range(1, len(nums)):
if nums[i][0] <= maxn:
res.append([nums[i][0], min(maxn, nums[i][1])])
maxn = max(maxn, nums[i][1])
return res
# 双指针方法
class Solution:
def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:
res = []
i, j = 0, 0
while i < len(firstList) and j < len(secondList):
l1, r1 = firstList[i][0], firstList[i][1]
l2, r2 = secondList[j][0], secondList[j][1]
if l1 <= r2 and r1 >= l2:
res.append([max(l1, l2), min(r1, r2)])
if r1 >= r2:
j += 1
else:
i += 1
return res