Medium

Interval List Intersections

075

Return all intersections between two sorted lists of disjoint intervals.

EXAMPLES

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
  ]
]

FUNCTION SHAPE

firstList: intMatrixsecondList: intMatrix→intMatrix

SOLUTION NOTE

We just do two pointers, if there is overlap add it. The interesting part is how do we decide to increment which pointer. This is completely greedy logic. The one that ends later serves more utility for us, because it provides more opportunity for future intersection, so let's keep it and discard the other.

Ie. [1,10] vs [2,5], [6,8]. Discarding [2,5] is the right choice, because later the [6,8] will intersect again with [1,10].

If we instead chose to discard based on earlier start time, then we would completely miss this [6,8] intersection.

It's important to be able to think ahead, and come up and reason about these edge cases before presenting your solution to your interviewer.

Reveal reference solution +

pythonREFERENCE

def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:
    m, n = len(firstList), len(secondList)
    i = j = 0
    res = []

    while i < m and j < n:
        a, b = firstList[i]
        c, d = secondList[j]

        overlap = max(a, c) <= min(b, d)

        if overlap:
            res.append([max(a, c), min(b, d)])

        if b < d:
            i += 1
        else:
            j += 1

    return res

TimeO(m + n)

SpaceO(m + n)

Open on LeetCode ↗