Merge and insert intervals: A Sample Coding Interview Solution

The coding question

You're given a list of time intervals sorted by start time and a new interval. Insert the new one and merge any that overlap, then return the result.

Ask a few questions first

Ask	What we'll assume
Do intervals that just touch count as overlapping?	Yes. [1, 2] and [2, 5] become [1, 5]. Ask, because some versions say no.
Can the list already have overlaps?	Usually it doesn't, but the same pass merges them anyway, so we'll handle it.
Can I change the input list?	We'll say no and build a new one.
What if the list is empty?	Return just the new interval.
How long is the list?	Up to about 10,000 intervals.

A couple of examples

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

Start with brute force

Add the new interval to the end, sort everything by start, then merge in one pass. It's short and correct, so it's a fine thing to say first.

Cost: O(n log n) because of the sort. That throws away the fact that the list is already sorted.

A better way

The list is already sorted, so the only thing out of place is the new interval. Walk the list once and slot the new one in before the first interval that starts after it. Now you're walking everything in start order without sorting.

Merging in start order is simple: keep a result list, and for each interval, either stretch the last one in the result (if this one starts at or before its end) or add it as a new entry.

You could find where the new interval goes with binary search, but you still have to copy the list into the result, so it's O(n) either way. Mention it, then keep the single pass.

Start with an empty result list.
Write a small add helper: if the result isn't empty and this interval starts at or before the last end, stretch the last end to the larger of the two. Otherwise append a copy.
Walk the intervals. Before adding one that starts after the new interval, add the new interval first, once.
If the loop ends and the new interval still isn't placed, add it at the end.
Return the result.

The code

solution.pypython

def insert_interval(intervals, new_interval):
    merged = []

    def add(interval):
        start, end = interval
        if merged and start <= merged[-1][1]:
            # Overlaps or touches the last one, so stretch it.
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])

    placed = False
    for interval in intervals:
        # Slot the new interval in before the first one that starts after it.
        if not placed and new_interval[0] < interval[0]:
            add(new_interval)
            placed = True
        add(interval)
    if not placed:
        add(new_interval)
    return merged

	Cost	Why
Time	O(n)	One pass over the list, and each interval is added or merged once
Space	O(n)	The result list. Nothing else grows

Test it

Walk through one of the examples out loud, then check the cases that tend to break things:

An empty list returns just the new interval.
A new interval that goes before everything or after everything is added at the start or the end.
A new interval inside an existing one, like [2, 3] into [[1, 5]], changes nothing.
Touching intervals merge, so [[1, 2], [5, 6]] with [2, 5] becomes one interval.
A new interval that swallows several old ones, like [4, 8] in the second example, merges them all.

Common mistakes

Using < instead of <= when checking overlap, so touching intervals stay separate.
Setting the merged end to the new interval's end instead of the larger of the two. [1, 10] with [2, 3] would shrink to [1, 3].
Forgetting to add the new interval when it goes after everything.
Appending the original lists instead of copies, then changing them when merging. That quietly edits the caller's input.

Follow-up questions

What if you had to insert many intervals over time?

Keep the intervals in a sorted structure, like a balanced tree keyed by start. Each insert finds its neighbors in O(log n) and only merges the ones it touches.

What if the list isn't sorted?

Sort by start first, then run the same merge pass. That's O(n log n).

How would you find free time between meetings?

Merge everything first, then the gaps between one interval's end and the next one's start are the free slots.

How the time adds up

Minutes	What you're doing
0–5	Ask questions and agree on examples
5–10	Brute force: append, sort, merge
10–20	Use the sorted order and walk once
20–35	Write the code
35–40	Test with the examples and edge cases
40–45	Follow-up questions

Key concepts used here

We wrote this sample solution ourselves. Practice Loop is independent and isn't affiliated with or endorsed by Amazon.