LeetCode 57 · Intervals

Insert Interval, explained with a picture

Squeezing a new booking into a calendar.

MediumIntervals
▶ Watch it step by step

The problem

Given non-overlapping intervals sorted by start, insert a new interval and merge wherever needed so the list stays sorted and non-overlapping.

Input:  [1,2] [3,5] [6,7] [8,10] [12,16], new [4,8]
Output: [1,2] [3,10] [12,16]

Picture it

Picture a calendar of bookings. Bookings that end before the new one starts stay as they are. Bookings that overlap the new one get melted into it (its start becomes the earliest start, its end the latest end). Bookings starting after it ends stay as they are.

How to recognise it

  • The input is a list of intervals that are already sorted and do not overlap, and one new interval arrives.
  • The output must stay sorted and non-overlapping, so anything the new interval touches has to be merged into it.
  • Because the list is sorted, it splits into three runs: intervals that end before the new one starts, intervals that overlap it, and intervals that start after it ends. Each run is contiguous.
  • Up to 10^4 intervals, and the sorting has already been done for you, so one pass is the target.
  • Here intervals that only touch ([1, 2] and [2, 3]) count as overlapping and are merged.

Start with brute force

Ignore the existing order: add the new interval, sort everything, and merge overlapping neighbours, exactly as in Merge Intervals.

def insert_brute(intervals, new):
    allv = sorted(intervals + [new])
    out = [list(allv[0])]
    for start, end in allv[1:]:
        if start <= out[-1][1]:
            out[-1][1] = max(out[-1][1], end)
        else:
            out.append([start, end])
    return out

Time is O(n log n) for the sort and space O(n). For 10^4 intervals that is still fast. The waste is the sort itself: the list was sorted and disjoint before, and only one interval is out of place.

From brute force to the idea

  1. Find the waste. Sorting re-orders n intervals that are already in order. Only the region around the new interval can change.
  2. Phase 1: copy what ends before. While intervals[i][1] < new[0], the interval finishes before the new one starts, so it is copied unchanged. The test is strict: an interval ending exactly at new[0] touches it and must be merged.
  3. Phase 2: absorb what overlaps. While intervals[i][0] <= new[1], the interval starts before the new one ends. Since phase 1 already skipped everything ending earlier, it must overlap. Stretch new to the smaller start and the larger end. Several intervals can be swallowed in a row.
  4. Add the merged interval. After phase 2, new covers everything it touched. Append it once.
  5. Phase 3: copy the rest. Every remaining interval starts after new ends, so out.extend(intervals[i:]) adds them in order.

This is the key idea: in a sorted list the new interval meets one contiguous run, so walk once, keeping, merging, then keeping again.

The key idea

Three phases: before, overlapping (merge), after. O(n).

Python solution

def insert(intervals, new):
    out, i, n = [], 0, len(intervals)
    while i < n and intervals[i][1] < new[0]:
        out.append(intervals[i]); i += 1          # ends before: keep
    while i < n and intervals[i][0] <= new[1]:
        new = [min(new[0], intervals[i][0]),       # overlaps: absorb it
               max(new[1], intervals[i][1])]
        i += 1
    out.append(new)
    out.extend(intervals[i:])                      # starts after: keep
    return out

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(n log n): sorting all intervals againO(n): the sorted copy and the output
Three phases (shown code)O(n): the index i only moves forward, each interval is looked at onceO(n): the output list; O(1) besides it

Edge cases

  • Empty list ([], new [5, 7]): both loops are skipped and the result is [[5, 7]].
  • New interval before everything ([[3, 5]], new [1, 2]): phase 1 copies nothing, [1, 2] is added first, then [3, 5].
  • New interval after everything ([[1, 2]], new [4, 5]): phase 1 copies [1, 2], then [4, 5] is appended.
  • Touching intervals ([[1, 2], [5, 6]], new [2, 3]): merged into [[1, 3], [5, 6]].
  • Swallowing many ([[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], new [4, 8]): returns [[1, 2], [3, 10], [12, 16]].
  • New interval inside one ([[1, 10]], new [3, 4]): returns [[1, 10]].
  • The input is not changed: new is replaced by a fresh list, not edited, but out shares the untouched interval lists with the input.

Common mistakes

  • Using <= in phase 1, which keeps an interval that only touches the new one separate instead of merging it.
  • Appending the merged interval inside phase 2, once per absorbed interval, which creates duplicates.
  • Comparing only with the first overlapping interval's end. The merged end is max(new[1], intervals[i][1]), because the new interval may reach past several.
  • Forgetting phase 3, which drops every interval after the new one.
Your turn: remove an interval

The intervals are now half-open ([a, b) contains a but not b), sorted and disjoint. Remove the range [x, y) from them and return what is left. For [[0, 2], [3, 4], [5, 7]] with [1, 6) removed, the answer is [[0, 1], [6, 7]]. Describe your approach, then write it if you like.

Compare with our answer

Still one pass over the sorted list. An interval that does not touch the cut is kept whole. One that does may leave a piece on the left (if it starts before x) and a piece on the right (if it ends after y), possibly both.

def remove_interval(intervals, cut):
    x, y = cut
    out = []
    for a, b in intervals:
        if b <= x or a >= y:          # no overlap: keep whole
            out.append([a, b])
        else:
            if a < x:
                out.append([a, x])    # piece left of the cut
            if b > y:
                out.append([y, b])    # piece right of the cut
    return out

Time O(n), space O(n) for the output.

A strong answer mentions: the no-overlap test for half-open intervals, the two possible leftover pieces, and that the output stays sorted without re-sorting.

Check what stuck

1. A list of 10^4 sorted, non-overlapping free slots must be updated after a meeting removes part of that time. Which approach fits best?

2. Why is the shown code O(n) rather than O(n log n)?

3. A learner changes phase 1 to intervals[i][1] <= new[0]. Which input now gives a wrong answer?

Score 60% or more and the lesson is marked complete.