What is the most efficient approach for solving the Interval List Intersections problem?

The most efficient approach is to use the two-pointer technique, where you traverse both lists simultaneously, tracking the current intersection and adjusting the pointers accordingly.

How does the two-pointer technique work for Interval List Intersections?

The two-pointer technique involves using two pointers, one for each list, and comparing the current intervals. If they overlap, we record the intersection and move the pointer of the interval with the smaller ending value.

What is the time complexity of the solution to the Interval List Intersections problem?

The time complexity of the solution is O(n + m), where n and m are the lengths of the two input lists, since both lists are traversed exactly once.

How do you handle cases where the intervals do not overlap in the Interval List Intersections problem?

If the intervals do not overlap, we move the pointer of the list with the smaller ending value to attempt finding a new intersection in the subsequent comparisons.

Can the Interval List Intersections problem be solved with a different algorithm?

While the two-pointer technique is the most efficient solution, you could solve it with a brute-force approach by checking all pairs of intervals, but this would lead to higher time complexity.

#986

Medium

auto_awesome双·指针·invariant

LeetCode 题解工作台

区间列表的交集

给定两个由一些闭区间组成的列表， firstList 和 secondList ，其中 firstList[i] = [start i , end i ] 而 secondList[j] = [start j , end j ] 。每个区间列表都是成对不相交的，并且已经排序。返回这两…

数组双指针扫描线

题目描述

给定两个由一些 闭区间 组成的列表，firstList 和 secondList ，其中 firstList[i] = [start_i, end_i] 而 secondList[j] = [start_j, end_j] 。每个区间列表都是成对 不相交 的，并且 已经排序 。

返回这 两个区间列表的交集 。

形式上，闭区间 [a, b]（其中 a <= b）表示实数 x 的集合，而 a <= x <= b 。

两个闭区间的交集是一组实数，要么为空集，要么为闭区间。例如，[1, 3] 和 [2, 4] 的交集为 [2, 3] 。

示例 1：

输入：firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]
输出：[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

示例 2：

输入：firstList = [[1,3],[5,9]], secondList = []
输出：[]

示例 3：

输入：firstList = [], secondList = [[4,8],[10,12]]
输出：[]

示例 4：

输入：firstList = [[1,7]], secondList = [[3,10]]
输出：[[3,7]]

提示：

0 <= firstList.length, secondList.length <= 1000
firstList.length + secondList.length >= 1
0 <= start_i < end_i <= 10⁹
end_i < start_i+1
0 <= start_j < end_j <= 10⁹
end_j < start_j+1

lightbulb

解题思路

方法一：双指针

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def intervalIntersection(
        self, firstList: List[List[int]], secondList: List[List[int]]
    ) -> List[List[int]]:
        i = j = 0
        ans = []
        while i < len(firstList) and j < len(secondList):
            s1, e1, s2, e2 = *firstList[i], *secondList[j]
            l, r = max(s1, s2), min(e1, e2)
            if l <= r:
                ans.append([l, r])
            if e1 < e2:
                i += 1
            else:
                j += 1
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate understands how to implement a two-pointer technique efficiently.
question_mark
They should be able to explain the trade-off of traversing both lists in a single pass rather than checking each pair of intervals individually.
question_mark
The candidate can identify the necessary conditions for intervals to overlap and the corresponding actions to move the pointers accordingly.

warning

常见陷阱

外企场景

error
Incorrectly handling cases where intervals do not overlap, resulting in missing intersections.
error
Failing to move the correct pointer after finding an intersection, leading to unnecessary comparisons.
error
Not keeping track of the current intersecting range properly, which could lead to incorrect results.

swap_horiz

进阶变体

外企场景

arrow_right_alt
The problem can be extended to find the union of two interval lists instead of the intersection.
arrow_right_alt
A variant could involve unsorted interval lists, requiring sorting before applying the two-pointer technique.
arrow_right_alt
The problem could also ask to handle intervals with more complex ranges, such as half-open intervals.

help

常见问题

外企场景

继续练习

#977 有序数组的平方 #969 煎饼排序 #962 最大宽度坡