Problem Breakdown
We need to compute the list of intersections between firstList and secondList.
- Inputs: Two lists (
firstList,secondList) where each element is a[start, end]pair. Both are sorted by start time and intervals within each list do not overlap (disjoint). - Output: A new list of closed interval pairs representing the intersection points between the two input lists. If no intersections exist, return an empty list.
- Constraints & Edge Cases:
- Inputs can be empty (
[]), but at least one must contain intervals based on constraints (though logic handles both empty). - Coordinates are up to , requiring pointer arithmetic rather than array mapping.
- Intersections can be single points where
start == end.
- Inputs can be empty (
Intuition
Since the input lists are sorted by start time and disjoint within themselves, we do not need nested loops (which would yield O(N*M)). Instead, a Two Pointers approach allows us to traverse both lists in linear time.
- We maintain pointers for each list (
iandj). - At any step, the interval that ends earlier cannot intersect with any future intervals from the other list because all subsequent intervals start after its end (due to sorting).
- Therefore, we always advance the pointer corresponding to the interval that finishes first. This ensures every element is visited at most once.
Approach
- Initialize pointers
i = 0andj = 0. - Loop while both pointers are within bounds of their respective lists.
- Identify current intervals:
intervalAfromfirstList[i]andintervalBfromsecondList[j]. - Compute the intersection range boundaries:
- Start is
max(intervalA.start, intervalB.start). - End is
min(intervalA.end, intervalB.end).
- Start is
- If valid overlap exists (
start <= end), add[start, end]to results. - Advance the pointer of whichever list’s current interval ends earlier (or equal). This discards intervals that have finished their potential intersection window relative to the other sorted stream.
Complexity Analysis
- Time Complexity: where N and M are lengths of
firstListandsecondList. Each element is processed exactly once by its respective pointer; no backtracking occurs. - Space Complexity: auxiliary space (excluding the output list which requires for K intersections).
Solution
class Solution:
def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:
i = 0
j = 0
result = []
while i < len(firstList) and j < len(secondList):
start1, end1 = firstList[i]
start2, end2 = secondList[j]
# Determine the intersection range boundaries
overlap_start = max(start1, start2)
overlap_end = min(end1, end2)
# If valid intersection exists (start <= end), add to result.
# This handles single-point overlaps correctly as well.
if overlap_start <= overlap_end:
result.append([overlap_start, overlap_end])
# Advance the pointer of the interval that ends first or equal.
# Once an interval finishes, it cannot intersect with subsequent intervals in the other list
# because they are sorted and disjoint within their own lists.
if end1 < end2:
i += 1
else:
j += 1
return result
Edge Cases Handled
- Empty Lists: If either
firstListorsecondListis empty, the loop condition fails immediately and an empty list is returned. - No Intersection: Disjoint intervals (e.g.,
[0,2]vs[5,10]) result in advancing pointers until one list is exhausted without adding results. - Single Point Overlap: The logic
overlap_start <= overlap_endcorrectly captures cases where start equals end (e.g., intersection at a single point). - One List Fully Contained: If an interval from one list is completely inside the other, the pointer for the inner interval advances first until it matches or exceeds bounds.