Coding interview problems › Intervals

📅 Intervals Medium

Merge Intervals

Merge Intervals explained: sort by start, then sweep once and fuse overlaps, O(n log n) tested Python, the touching-endpoints trap and a live timeline visual.

Also searched as: merge overlapping intervals · merge intervals sort and sweep · combine overlapping ranges

📅

Try it live Free

Merge Intervals & Meeting Rooms

Drag intervals on the timeline and watch overlaps fuse into busy blocks after the sort-by-start, sweep-once move.

Also useful: Sorting Race: Insertion vs Merge vs Quick

Open the playground →

The problem

Given a list of intervals [start, end], merge every group of overlapping intervals and return the resulting non-overlapping intervals. Intervals that touch at an endpoint, like [1, 4] and [4, 5], count as overlapping.

Input[[1, 3], [2, 6], [8, 10], [15, 18]]
Output[[1, 6], [8, 10], [15, 18]]
Input[[1, 4], [4, 5]]
Output[[1, 5]]

The key insight

After sorting by start, any interval that overlaps the current merged block must come right after it. So sweep once: if the next interval starts at or before the current block's end, stretch the end; otherwise close the block and start a new one.

Brute force first: Comparing every pair of intervals and merging repeatedly until nothing changes is O(n²) or worse.

Step-by-step approach

  1. Sort the intervals by start.
  2. Put the first interval in the output as the current block.
  3. For each next interval, if its start is <= the last block's end, set that end to the larger of the two ends.
  4. Otherwise append the interval as a new block.
  5. Return the output.

Python solution

PYTHON 3tested
def merge(intervals):
    out = []
    for start, end in sorted(intervals):
        if out and start <= out[-1][1]:        # overlaps the last block
            out[-1][1] = max(out[-1][1], end)
        else:
            out.append([start, end])
    return out

Complexity

TimeO(n log n)
SpaceO(n)

Sorting dominates. The sweep itself is a single O(n) pass. The output can hold up to n intervals.

Common mistakes

Frequently asked questions

What is the time and space complexity of Merge Intervals?

O(n log n) time for the sort plus O(n) for the sweep, and O(n) space for the output (Python's sort also uses up to O(n) extra).

Why do we sort by start time and not end time?

Sorted by start, every interval that could overlap the current block appears immediately after it, so one comparison with the block's end decides. Sorting by end does not give that guarantee for merging.

How do I handle a stream of intervals arriving one by one?

Keep the merged intervals in a balanced tree or sorted list keyed by start. Each new interval finds its neighbours by binary search and merges with any that overlap.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Intervals Merge Intervals & Meeting Rooms lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.