Merge intervals: the sort-and-sweep solution, step by step

In this article

1. Before you start
2. Why interviewers ask this
3. Merge intervals from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

Why interviewers ask this

Interval problems form a family of coding-round questions, and the question is rarely only "merge these". It is the first rung of a ladder that continues into free-time search, meeting rooms and schedule checks, so a clean answer here sets up every follow-up. Interviewers use it to see whether you notice that sorting turns a messy comparison of every pair into a single pass, and whether you handle the edge cases without being told: touching ranges, a long range that swallows short ones, an empty list.

A weak answer compares every pair of intervals and loses track of which ones are already merged. A strong answer names the sort key, states the overlap test in one line, and says why the total cost is that of the sort. Other coding-round patterns are collected in the coding interviews guide.

Merge intervals from first principles

Merge intervals

Merge intervals is a problem and a technique in which a list of intervals is turned into the shortest list of non-overlapping intervals that covers exactly the same points, by sorting on the start value and joining each interval to the block before it when they overlap.

Interval

An interval is a pair of numbers, a start and an end with the start no larger than the end, that stands for every point from the start to the end, such as a meeting from 9 to 11.

Big-O notation

Big-O notation is a way to describe how the number of steps grows with the input size n, ignoring constant factors: O(n) means steps grow in proportion to n, and O(n log n) means roughly n times the base-2 logarithm of n. For n = 10,000, n log2 n is about 132,877, close to the 119,779 comparisons measured for the sort, while the merge pass makes n - 1 = 9,999 comparisons.¹

Sweep

A sweep is a single pass over sorted data in which you keep a small running state, here the current block, and update it at each item instead of comparing the item with all the others.

In plain words

Picture strips of tape laid on a ruler. Some overlap and some leave a gap. Merging asks which pieces of tape remain if you fuse every overlapping strip. Slide your finger along the ruler from the left, holding the right-hand tip of the piece you are building. When the next strip starts before your tip, it joins the piece. When it starts after, the piece is finished and a new one begins.

The analogy breaks in one place. On a ruler you see every strip at once and spot gaps by eye. Code sees one interval at a time, so it needs the sort to ensure that nothing left of the current strip can still matter. Two intervals overlap when the start of the later one is at or before the end of the earlier one.

Step 1: Sort the intervals by their start

The first step puts the intervals in order of start value. The input is the list as given, in any order; the output is the same intervals ordered by start. Sorting is what makes one pass enough, because after it every interval that could overlap the current block sits next to it, and nothing earlier can reach forward past the block's end.

In Python, sorted(intervals, key=lambda p: p[0]) does it, and the key is evaluated once per item (Python guide to sorting techniques, read 2026-10-24). Sorting on the start alone is enough; ties between equal starts do not affect the result, so you do not need a second key. A stable sort, one that keeps equal items in their original order, is what list.sort provides (Python documentation, read 2026-10-24), but this algorithm does not rely on it.

Step 2: Open a block with the first interval

The second step creates the running state. The input is the sorted list; the output is a result list holding one block, a copy of the first interval. A block is the merged interval you are currently building, and it is the last item of the result list, so you can always read and change it in constant time.

If the input is empty there is no first interval, so return an empty list straight away; this is an edge case to handle first. Copying the pair matters in languages where a pair is a reference: if the block shares storage with the input, extending it later also changes the caller's data, a side effect that surprises people. Everything else in the algorithm touches only this one block and the interval being examined.

Step 3: Test the next start against the block's end

The third step decides whether the next interval joins the block. The input is the next interval and the current block; the output is a yes or no. The test is one line: the next start is less than or equal to the block's end. Use at-or-before, not strictly before, when ranges that touch at a point, such as 1 to 4 and 4 to 5, should merge into 1 to 5. If the problem says touching ranges stay separate, you switch to strictly before, and the only way to know is to ask. This single operator matters: on 5,000 random inputs, strictly-before changed the answer on 1,473.¹ Ask the interviewer about touching ranges before you write the line.

Step 4: Extend the block or start a new one

The fourth step acts on the answer. If the test said yes, set the block's end to the larger of its current end and the new interval's end. If it said no, the block is finished, so append the new interval as the next block.

Take the larger end, not simply the new one, because an interval can sit entirely inside the block: with 1 to 10, 2 to 3 and 4 to 8, copying the new end would shrink the block to 1 to 3 and then leave 4 to 8 as a separate block.¹ After the last interval, the result list is the answer. Each interval after the first was compared exactly once, with the block, so this pass is linear in the number of intervals.

1 · Sort by start2 · Open a block3 · Test the next start4 · Extend or newReplay

Step-by-step description

1. Order the intervals by their start value.
2. The first interval is the current block.
3. Overlap means start is at or before the block end.
4. Take the larger end, or start a new block.

• Sort the intervals by start first.
• The first interval opens the current block.
• The next interval overlaps the block when its start is at or before the block's end.
• Extend the block's end to the larger of the two ends, or start a new block.

Worked example

The input is 1 to 3, 2 to 6, 8 to 10 and 15 to 18, already in start order (illustrative values chosen for this page). The block starts as 1 to 3. The next start, 2, is at or before 3, so the end becomes the larger of 3 and 6, which is 6. The next start, 8, is after 6, so 1 to 6 is closed and 8 to 10 opens. The next start, 15, is after 10, so 8 to 10 is closed and 15 to 18 opens. The result is 1 to 6, 8 to 10 and 15 to 18.¹ Four intervals became three blocks.

Text description of the diagram

• The inputs are 1 to 3, 2 to 6, 8 to 10 and 15 to 18.
• The merged result is 1 to 6, 8 to 10 and 15 to 18.
• Only the first two intervals overlap, so four inputs become three blocks.

Here is the function from the script that produced those numbers, with longer names.

def merge(intervals):
    blocks = []
    for start, end in sorted(intervals, key=lambda p: p[0]):
        if blocks and start <= blocks[-1][1]:       # overlaps the current block
            blocks[-1][1] = max(blocks[-1][1], end)  # extend with the larger end
        else:
            blocks.append([start, end])             # open a new block
    return blocks

The loop appends a new two-item list for each block, so the caller's input is never changed. The script also counted the comparisons made by the sort on random start values: 23 for 10 intervals, 532 for 100, 8,680 for 1,000 and 119,779 for 10,000, against 9, 99, 999 and 9,999 for the merge pass.¹

Text description of the diagram

• For 10,000 random intervals the sort makes 119,779 comparisons.
• For the same input the merge pass makes 9,999 comparisons.

Trade-offs and edge cases

Time and space. Timsort sorts in O(n log n) comparisons in the worst case and O(n) extra space; it was Python's sort until version 3.11 replaced it with Powersort, a derived algorithm with a more robust merge policy and the same bounds (Wikipedia, Timsort, edited 8 October 2026). The pass adds O(n), so the total is O(n log n) time and O(n) space for the result.

The cost chart above is dominated by the sort because n log n grows faster than n. Already sorted input. If the intervals arrive sorted by start, skip the sort and the whole merge is O(n). Closed or half-open. Whether 1 to 4 and 4 to 5 touch depends on the problem; meeting rooms usually treat an end at 10 and a start at 10 as compatible, while a merge usually joins them.

Related problems. Choosing the most non-overlapping intervals is a different task: the greedy rule picks the earliest finishing interval first, also in O(n log n) time (Wikipedia, Interval scheduling, edited 9 November 2025). Do not mix the two rules: merging sorts by start, selection sorts by end. A single pass with a small running state is also the core of the monotonic stack technique, and topological sort also processes items in an order it builds as it goes, with a queue in place of a sort. When clashes are exact matches, such as two bookings of the same slot id, a hash set finds them in one pass without a sort; overlap between ranges still needs the sort.

How to answer it in an interview

The spoken structure is: sort, test, extend with the maximum, then state the cost.

Common mistakes

Skipping the sort. (wrong) "I loop through the list once and merge as I go." The input order is arbitrary, so a later interval can belong to an earlier block. With 8 to 10, 1 to 3, 2 to 6, 15 to 18, the unsorted loop returns only 8 to 10 and 15 to 18, and across 5,000 random inputs it was wrong on 3,080.¹ (right) "I sort by start first, so every interval that could join the block is next in line."

Copying the new end. (wrong) "If they overlap, the block's end becomes the new interval's end." (right) "The block's end becomes the larger of the two ends." For 1 to 10, 2 to 3 and 4 to 8, the wrong rule returns 1 to 3 and 4 to 8.¹

A strict comparison by habit. (wrong) "They overlap if the start is less than the end." (right) "They overlap if the start is at or before the end, unless the problem says touching ranges stay apart." Ask first.

Forgetting the empty list. (wrong) Reading the first interval of an empty input crashes. (right) "If the list is empty I return an empty list."

Text description of the diagram

• With 8 to 10, 1 to 3, 2 to 6, 15 to 18, the unsorted loop returns only 8 to 10 and 15 to 18.
• For 1 to 10, 2 to 3 and 4 to 8, the wrong rule returns 1 to 3 and 4 to 8.
• They overlap if the start is at or before the end, unless the problem says touching ranges stay apart.

Follow-up questions

How do you merge two sorted interval lists?

Merge them like the last step of merge sort, always taking the list whose next interval starts earlier, and apply the same sweep to that stream. No second sort is needed, so the cost is linear in the combined length of the two lists. The sweep itself is unchanged.

How do you find the free time between intervals?

Merge first, then read the gaps between consecutive blocks, plus the gap before the first block and after the last one inside the window. For the example blocks 1 to 6, 8 to 10 and 15 to 18 in a window from 0 to 20, the free spans are 0 to 1, 6 to 8, 10 to 15 and 18 to 20.¹

How do you find the time of maximum overlap?

Turn each interval into two events, plus one at the start and minus one at the end, sort the events with ends before starts at equal times, and keep a running count. For the meetings 9 to 11, 10 to 12, 10 to 13 and 14 to 15 (illustrative), the count peaks at 3 at time 10.¹

How do you check whether a new booking fits a schedule?

The new booking must sit inside the opening window and clear every existing booking, meaning it ends at or before that booking's start or starts at or after its end. With bookings sorted by start, only the booking just before and just after the new start need the test.

With bookings 10 to 12 and 13 to 15 in a window from 10 to 23, a booking from 12 to 13 fits, 11 to 14 does not, and 22 to 24 runs past closing. A booking from 12 to 14 clashes with 13 to 15, one from 11 to 12 clashes with 10 to 12, and one from 10 to 20 overlaps 10 to 12 and swallows 13 to 15 whole, so each of those fails the test too.¹

What if the intervals arrive one at a time?

Keep the blocks in a sorted structure. A new interval is found by search, merged with every block it overlaps, and the replaced blocks removed. That costs a search plus the merges per arrival, instead of re-sorting everything. For another one-pass pattern, see longest substring without repeating characters; for a problem that also starts by ordering items by a key, k closest points to the origin; and for how rounds like this fit together, interview loops.

Sources

1. Built-in Types: list.sort (Python 3 documentation) — Python Software Foundation (date = read date), 24 Oct 2026
2. Sorting Techniques (Python guide) — Python Software Foundation (date = read date), 24 Oct 2026
3. Timsort — Wikipedia (last edited 8 October 2026), 8 Oct 2026
4. Interval scheduling — Wikipedia (last edited 9 November 2025), 9 Nov 2025