noodleProblems/
Interval List Intersections
#124

Interval List Intersections

AlgorithmmediumArrayTwo Pointers

You are given two lists of closed intervals, firstList and secondList, where each list[i] = [start_i, end_i]. Each list is pairwise disjoint and **sorted in ascending order by start**.

Return the intersection of the two interval lists: the list of closed intervals covered by *both* inputs, sorted by start. The intersection of two closed intervals [a, b] and [c, d] is [max(a, c), min(b, d)] — and it exists only when max(a, c) <= min(b, d) (touching endpoints count, so an intersection can be a single point like [5, 5]).

Example cases

  • interleaved
    in firstList =
    02
    510
    1323
    2425
    secondList =
    15
    812
    1524
    2526
    out [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
    Each output interval is covered by one interval from each list; e.g. [5,10] ∩ [1,5] = [5,5].
  • empty second list
    in firstList =
    13
    59
    secondList = []
    out []
    With nothing to intersect against, the result is empty.
  • contained
    in firstList =
    17
    secondList =
    310
    out [[3,7]]

Constraints

  • 0 <= firstList.length, secondList.length <= 1000
  • firstList.length + secondList.length >= 1
  • 0 <= start_i <= end_i <= 10^9
  • Each list is pairwise disjoint and sorted by start.
Saved
firstList =
[[0,2],[5,10],[13,23],[24,25]]
secondList =
[[1,5],[8,12],[15,24],[25,26]]