Insert Interval

The problem

An interval [start, end] covers every number from start to end, with start at most end. intervals is a list of intervals sorted by start, and no two of them overlap. Here two intervals overlap when they share at least one number, so intervals that only touch at an end, such as [1, 2] and [2, 5], overlap too. Add newInterval to the list: join it with every interval it overlaps into one interval that covers them all. Return the whole list, still sorted by start and with no overlaps left. intervals may be empty, and numbers may be negative.

What to write

function solve(intervals: number[][], newInterval: number[]): number[][]

Input
intervals = [[1,3],[6,9]]
newInterval = [2,5]

Output
[[1,5],[6,9]]

Input
intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]]
newInterval = [4,8]

Output
[[1,2],[3,10],[12,16]]

Constraints

0–1,000 sorted disjoint closed intervals; touching endpoints merge.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   The list is already sorted by start, and its intervals neither overlap nor touch one another. So you never need to sort, and the intervals that the new one overlaps, if there are any, sit side by side in the list.

2. Hint 2: Ask a smaller question

   Take the list [1, 2], [3, 5], [6, 7], [8, 10], [12, 16] and the new interval [4, 8]. Which intervals reach the answer unchanged, and which do not? What single comparison tells you that [1, 2] is safe?

3. Hint 3: Name the pattern

   Walk the list once from left to right. First come the intervals that end before the new one starts, then the ones that overlap it, then the ones that start after it ends. Handling intervals one by one in sorted order is a sorted interval sweep. The signal: the intervals are already in order. Read the lesson on sorted interval sweep.

4. Hint 4: State the invariant

   While you merge, the new interval is a start and an end that only move outward. At every moment the two ends cover the original new interval and every list interval absorbed so far, and every interval copied to the answer ends before that start.

5. Hint 5: Sketch the pseudocode

   start, end = newInterval. Copy intervals to the answer while they end before start. Then, while the next interval starts at or before end: start = the smaller of the two starts, end = the larger of the two ends. Add [start, end]. Copy the intervals that are left.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Copy intervals ending before the new one. Merge all overlaps into the new interval, append it, then copy the remaining intervals.

The slow way

Add the new interval to the list, sort the whole list by start again, and then merge overlapping neighbors as if you knew nothing about the input. It is correct, but sorting takes about n log n steps, and the list was already in order before the one new interval arrived.

The insight

Because the list is sorted and its intervals do not overlap, reading it from left to right gives three stretches: intervals that end before the new one starts, intervals that overlap it, and intervals that start after it ends. Only the middle stretch changes. Together with the new interval it becomes one interval.

Step by step

1. Start an empty answer and hold the new interval's start and end. The new interval may grow when it meets others, so its two ends are kept as numbers that can change. The answer is built as a separate list.
2. Copy every interval that ends before the new one starts. Such an interval lies entirely to the left of the new one and does not even touch it. The list is sorted, so these intervals come first and go into the answer unchanged.
3. The next interval starts at or before the new end: they overlap. Everything that ends before the new start is already copied, so this interval ends at or after the new start. If it also starts at or before the new end, the two share at least one number.
4. Widen the new interval to cover the one that overlaps it. One interval must cover both, so it starts at the smaller of the two starts and ends at the larger of the two ends. An interval that lies inside the new one changes nothing.
5. No more overlaps: add the widened new interval. The loop stopped at an interval that starts after the new end, or at the end of the list. Later intervals start later still, so the new interval is finished. If nothing overlapped, it is added as it came.
6. Copy the intervals that are left, then return the answer. Each of them starts after the widened interval ends, so none can overlap it. They are already in order and go into the answer unchanged.

The same numbered steps are the comments in each solution.

function solve(intervals, newInterval) {
  // 1. Start an empty answer and hold the new interval's start and end
  const out = [];
  let [a, b] = newInterval,
    i = 0;
  // 2. Copy every interval that ends before the new one starts
  while (i < intervals.length && intervals[i][1] < a)
    out.push([...intervals[i++]]);
  // 3. The next interval starts at or before the new end: they overlap
  while (i < intervals.length && intervals[i][0] <= b) {
    // 4. Widen the new interval to cover the one that overlaps it
    a = Math.min(a, intervals[i][0]);
    b = Math.max(b, intervals[i++][1]);
  }
  // 5. No more overlaps: add the widened new interval
  out.push([a, b]);
  // 6. Copy the intervals that are left, then return the answer
  while (i < intervals.length) out.push([...intervals[i++]]);
  return out;
}

function solve(
  intervals: number[][],
  newInterval: number[],
): number[][] {
  // 1. Start an empty answer and hold the new interval's start and end
  const out = [];
  let [a, b] = newInterval,
    i = 0;
  // 2. Copy every interval that ends before the new one starts
  while (i < intervals.length && intervals[i][1] < a)
    out.push([...intervals[i++]]);
  // 3. The next interval starts at or before the new end: they overlap
  while (i < intervals.length && intervals[i][0] <= b) {
    // 4. Widen the new interval to cover the one that overlaps it
    a = Math.min(a, intervals[i][0]);
    b = Math.max(b, intervals[i++][1]);
  }
  // 5. No more overlaps: add the widened new interval
  out.push([a, b]);
  // 6. Copy the intervals that are left, then return the answer
  while (i < intervals.length) out.push([...intervals[i++]]);
  return out;
}

def solve(intervals, newInterval):
    # 1. Start an empty answer and hold the new interval's start and end
    out = []
    start, end = newInterval
    i = 0
    # 2. Copy every interval that ends before the new one starts
    while i < len(intervals) and intervals[i][1] < start:
        out.append(list(intervals[i]))
        i += 1
    # 3. The next interval starts at or before the new end: they overlap
    while i < len(intervals) and intervals[i][0] <= end:
        # 4. Widen the new interval to cover the one that overlaps it
        start = min(start, intervals[i][0])
        end = max(end, intervals[i][1])
        i += 1
    # 5. No more overlaps: add the widened new interval
    out.append([start, end])
    # 6. Copy the intervals that are left, then return the answer
    while i < len(intervals):
        out.append(list(intervals[i]))
        i += 1
    return out

Example 2, traced

Input
intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]]
newInterval = [4,8]

Output
[[1,2],[3,10],[12,16]]

Why it works

An interval is copied in front only if it ends before the new start, and behind only if it starts after the widened end, so no copied interval shares a number with the widened one. Every other interval overlaps it and lies between its two ends. The three groups are written in order, so the answer stays sorted.

Time and space

Time O(n), extra space O(n) output. Each interval is handled once, by exactly one of the three loops, with a fixed amount of work, so the time is O(n). The answer holds at most n + 1 intervals, which is the O(n) output. Besides the answer, only three numbers are stored.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Touching counts as overlapping here. If the first loop also copies an interval that ends exactly at the new start, [-8, 2] with the new interval [2, 10] comes back as two intervals instead of [-8, 10].
• Set the end to the larger of the two ends, not to the absorbed interval's end. In example 1, [2, 5] would shrink to [1, 3], and the answer would be the original list with the new interval gone.
• Add the new interval after the merging loop, whether or not that loop ran. If it is added only when something overlapped, an empty list returns an empty answer instead of the new interval.

Pattern

Sorted interval sweep.

Keep going