Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumsweep-line

Remove Interval

Problem (restated)

A sorted list of disjoint half-open intervals [start, end), and one interval toBeRemoved = [a, b) to subtract. Return the remaining pieces, still sorted and disjoint.

Intuition

Each input interval is independent (they do not overlap). Against [a, b) it either survives whole (no overlap), disappears (fully covered), or splits into the leftover left [s, a) and/or right [b, e) pieces.

Approaches

Clip each interval

Unverified

Time O(n)Space O(n)

Idea. For [s, e): if e ≤ a or s ≥ b, keep it. Else emit [s, a) when s < a and [b, e) when e > b.

Walkthrough. [[0,2],[3,4],[5,7]] minus [1,6] → [0,1] and [6,7]. [[0,5]] minus [2,3] → [0,2],[3,5].

Trade-offs. Linear because the input is already sorted and disjoint. Endpoints are half-open, so e == a does not overlap. Empty leftovers (s == a or e == b) are skipped by the strict inequalities.

Solution

export function removeInterval(intervals: number[][], toBeRemoved: number[]): number[][] {
  const a = toBeRemoved[0]!, b = toBeRemoved[1]!;
  const res: number[][] = [];
  for (const iv of intervals) {
    const s = iv[0]!, e = iv[1]!;
    if (e <= a || s >= b) res.push([s, e]);
    else {
      if (s < a) res.push([s, a]);
      if (e > b) res.push([b, e]);
    }
  }
  return res;
}

export function removeInterval(intervals: number[][], toBeRemoved: number[]): number[][] {
  const a = toBeRemoved[0]!, b = toBeRemoved[1]!;
  const res: number[][] = [];
  for (const iv of intervals) {
    const s = iv[0]!, e = iv[1]!;
    if (e <= a || s >= b) res.push([s, e]);
    else {
      if (s < a) res.push([s, a]);
      if (e > b) res.push([b, e]);
    }
  }
  return res;
}

Template connection

A one-interval sweep: the remove range is the only “active” event, and each input interval is clipped against it. Same leftover-left / leftover-right split you get when an exit event punches a hole in the skyline.

Reflection

Intervals are half-open [s, e). Keep one that lies fully left or fully right: e <= a or s >= b. An overlap is cut out of the middle.
When s < a, keep [s, a). When e > b, keep [b, e). Both can happen, and then one interval becomes two.
A full cover is dropped. e == a does not overlap, so the interval stays. The output keeps the input order.