Medium

Remove Interval

LAB

Given disjoint sorted intervals, remove toBeRemoved from them and return the remaining interval pieces.

EXAMPLES

Example 1

Input
{
  "intervals": [
    [
      0,
      2
    ],
    [
      3,
      4
    ],
    [
      5,
      7
    ]
  ],
  "toBeRemoved": [
    1,
    6
  ]
}

Output
[
  [
    0,
    1
  ],
  [
    6,
    7
  ]
]

FUNCTION SHAPE

intervals: intMatrixtoBeRemoved: intArray→intMatrix

SOLUTION NOTE

This should be fairly straightforward, just look at the 3 examples. If there is no overlap, add the segment. If there is overlap, then we have 3 segments: the one before overlap, the overlap, and the one after overlap. If any of them are not single points, we add them to res. (it's possible the segment is like [5,5] for example)

Reveal reference solution +

pythonREFERENCE

def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:
    c, d = toBeRemoved
    res = []

    for a, b in intervals:
        overlap = max(a, c) < min(b, d)

        if overlap:
            first = [a, max(a, c)]  # before overlap
            second = [min(b, d), b]  # after overlap

            for x, y in [first, second]:
                if x < y:
                    res.append([x, y])
        else:
            res.append([a, b])

    return res

TimeO(n)

SpaceO(n)

Open on LeetCode ↗