Merge Intervals in Python: Sorting Patterns for Interviews

Interval questions look like four different problems: merge them, insert into them, schedule rooms for them, delete the fewest of them. Underneath, they are one sort and one sweep, and the only decisions are which key to sort by and what a boundary touch means. Get those two decisions right and each of the four problems is about ten lines of Python.

Here is the cheat table to keep in your head. The sections after it justify each row and show the code, and every output printed below is from a real run.

Step zero: do touching intervals overlap?

Before writing anything, settle what [1, 4] and [4, 5] mean. If the endpoints are inclusive, they share the point 4 and should merge into [1, 5]. If a meeting ends exactly when the next begins, they do not conflict. The problem statement decides, and the whole solution hinges on one character: <= versus <.

merge([[1,4],[4,5]])         -> [[1, 5]]            # with <=
merge_strict([[1,4],[4,5]])  -> [[1, 4], [4, 5]]    # with <

Merge Intervals uses <= (touching counts). Meeting Rooms and Non-overlapping Intervals use the opposite convention (touching is fine). Ask the interviewer out loud, because silently guessing wrong passes every test except the one that matters.

Merge Intervals

Sort by start. Then each interval either overlaps the last merged one, in which case you stretch its end with max, or starts a new block. The max is essential, because a later interval can sit entirely inside the previous one.

def merge(intervals):
    intervals = sorted(intervals)
    out = [intervals[0][:]]            # copy, so the input is not mutated
    for s, e in intervals[1:]:
        if s <= out[-1][1]:
            out[-1][1] = max(out[-1][1], e)
        else:
            out.append([s, e])
    return out

merge([[1,3],[2,6],[8,10],[15,18]])   # -> [[1, 6], [8, 10], [15, 18]]
merge([[1,10],[2,3],[4,5]])           # -> [[1, 10]]

The second call is the bug magnet. A version that writes out[-1][1] = e would shrink the block to [1, 5]. The code assumes a non-empty list, so add a guard if your problem allows empty input. In a 3,000-case random test, this function matched a brute-force coverage check on every case.

Insert Interval: no sort needed

The list is already sorted, so a single left-to-right pass with three phases is enough, and it is the one problem here that runs in O(n).

def insert(intervals, new):
    res, i, n = [], 0, len(intervals)
    while i < n and intervals[i][1] < new[0]:      # 1. entirely before
        res.append(intervals[i]); i += 1
    while i < n and intervals[i][0] <= new[1]:     # 2. overlapping: absorb
        new = [min(new[0], intervals[i][0]), max(new[1], intervals[i][1])]
        i += 1
    res.append(new)
    res.extend(intervals[i:])                       # 3. entirely after
    return res

insert([[1,3],[6,9]], [2,5])                        # -> [[1, 5], [6, 9]]
insert([[1,2],[3,5],[6,7],[8,10],[12,16]], [4,8])   # -> [[1, 2], [3, 10], [12, 16]]

Notice the two loop conditions are complements of each other: “ends before the new one starts” and “starts before the new one ends”. Whatever fails both is automatically in phase three.

Meeting Rooms II: two solutions worth knowing

How many rooms do you need so that no two meetings in the same room overlap? Think of rooms as a pool. Sort by start time, and keep a min-heap of the end times of the rooms in use. When a meeting starts, if the earliest-ending room is already free, reuse it. Otherwise open a new one. The heap size at the end is your answer.

import heapq

def min_meeting_rooms(intervals):
    heap = []                           # end times of rooms in use
    for s, e in sorted(intervals):
        if heap and heap[0] <= s:
            heapq.heapreplace(heap, e)  # reuse the room that frees up first
        else:
            heapq.heappush(heap, e)     # all busy, open a new room
    return len(heap)

The sweep version drops the heap. Sort the starts and the ends separately and walk through the starts with a pointer on the ends:

def min_meeting_rooms_sweep(intervals):
    starts = sorted(s for s, _ in intervals)
    ends = sorted(e for _, e in intervals)
    rooms = j = 0
    for s in starts:
        if s < ends[j]:
            rooms += 1                  # nothing has ended yet, need a room
        else:
            j += 1                      # a room freed up, reuse it
    return rooms

min_meeting_rooms([[0,30],[5,10],[15,20]])   # -> 2
min_meeting_rooms([[7,10],[2,4]])            # -> 1

Both returned the same answers on the examples, and on 3,000 random schedules the heap version and the sweep version agreed every time. The heap is easier to explain, the sweep is shorter. If the heap part is new to you, the heapq guide covers the operations used here.

Non-overlapping Intervals: the sort key flips

This one asks for the minimum number of intervals to remove so the rest do not overlap. Equivalently, keep as many as possible. The greedy choice is to always keep the interval that ends earliest, since that leaves the most room for the future. So you sort by end, not start.

def erase_overlap_intervals(intervals):
    intervals.sort(key=lambda x: x[1])      # by END
    end = float('-inf')
    keep = 0
    for s, e in intervals:
        if s >= end:                        # touching is allowed here
            keep += 1
            end = e
    return len(intervals) - keep

erase_overlap_intervals([[1,2],[2,3],[3,4],[1,3]])   # -> 1
erase_overlap_intervals([[1,2],[1,2],[1,2]])         # -> 2
erase_overlap_intervals([[1,2],[2,3]])               # -> 0

Why not sort by start, as in the other problems? Try [[1,10],[2,3],[4,5],[6,7]]. Sorting by start grabs the long [1,10] first, which blocks everything else. The real results for that input:

erase by end:   1     # drop [1,10], keep three short ones
erase by start: 3     # wrong

The same “finish early to leave room” reasoning is the heart of the greedy algorithms guide, which also shows how to check whether a greedy choice is safe.

Mistakes that cost the most

• Forgetting to sort, or sorting by the wrong end of the interval.
• Replacing instead of extending the merged end (= e rather than max(...)).
• Mutating the input by returning references to the original lists, then editing them.
• Guessing the boundary rule instead of asking whether touching intervals overlap.
• Assuming the array is sorted when only Insert Interval promises it.

Complexity

Everything here is dominated by the sort, so O(n log n) time, plus O(n) space for the output or the heap. Insert Interval is the exception at O(n) time. When the input is already sorted or the values are small integers, a difference array or prefix sums can beat the sort. For Python helpers like sorted with a key, the Python interview cheat sheet has a quick reference, and the pointer-walking style of the sweep is cousin to the two pointers technique.

Good practice set: Merge Intervals, Insert Interval, Meeting Rooms I and II, Non-overlapping Intervals, Minimum Number of Arrows to Burst Balloons and Interval List Intersections. Say the boundary rule before you write each one.