Skip to main content
DSA patterns

Merge Intervals

mediumIntervals Must-doAWSAzureGCPHashiCorp

Problem statement

You're given a list of intervals, where each interval is a pair [start, end]. Two intervals overlap if one starts before or exactly when the other ends. Merge every group of overlapping intervals into a single interval that spans all of them, and return the resulting list of intervals, none of which overlap any other.

The intervals can be given in any order.

This is the same job as collapsing a list of maintenance windows or time-based access grants: if two windows touch or overlap, they should be reported as one combined window instead of two separate ones.

Examples

Example 1

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]

Output: [[1,6],[8,10],[15,18]]

Explanation: [1,3] and [2,6] overlap because 2 (the second interval's start) is inside [1,3], so they combine into [1,6]; the other two intervals don't touch anything, so they stay as they are.

Example 2

Input: intervals = [[1,4],[4,5]]

Output: [[1,5]]

Explanation: the first interval ends exactly where the second one starts, and touching counts as overlapping, so they merge into one interval covering 1 to 5.

Example 3

Input: intervals = [[4,7],[1,4]]

Output: [[1,7]]

Explanation: the intervals are given out of order, but [1,4] and [4,7] still touch at 4, so they merge into [1,7] regardless of the order they were listed in.

Hints

Hint 1: Two intervals can only be compared for overlap once you know which one starts first — sorting by start value turns a messy, any-order list into something you can scan left to right.

Approach

Optimal: Sort + single pass

Intuition

Once the intervals are sorted by start, the only interval a new one can possibly overlap with is the very last one you've added to your result — anything earlier has already been closed off, and nothing later has been seen yet. That means there's no need to look ahead or revisit anything: keep one "current group" going, and for each new interval either fold it into that group (if its start reaches inside the group) or close the group off and start a fresh one. This is what removes the repeated scanning from the brute force — each interval is looked at exactly once.

Steps

  1. Sort the intervals by their start value.
  2. Start the result list with the first interval.
  3. For every remaining interval, in order, compare its start against the end of the last interval in the result.
  4. If the start is less than or equal to that end, they overlap: update the last interval's end to the larger of the two ends.
  5. Otherwise, they don't overlap: add this interval to the result as a new, separate group.
  6. After the loop, the result holds every merged interval.

Dry run

intervals = [[1,3],[2,6],[8,10],[15,18]] (already sorted by start)

interval compare to last result end action result
[1,3] (nothing yet) starts the result [[1,3]]
[2,6] 2 ≤ 3 → overlaps extend last end to max(3,6)=6 [[1,6]]
[8,10] 8 ≤ 6? no new group [[1,6],[8,10]]
[15,18] 15 ≤ 10? no new group [[1,6],[8,10],[15,18]]

Only one comparison per interval, and each decision is final — nothing is ever revisited, unlike the brute force's repeated forward scans.

Edge cases: a single interval is returned exactly as given, since the loop never runs; when intervals only touch at a single point (like [1,4] and [4,5]), the <= comparison correctly treats them as overlapping and merges them.

Complexity

Time O(n log n) - Sorting the n intervals by start value costs O(n log n) and dominates the rest; the single pass that follows looks at each interval exactly once, which is O(n).

Space O(n) - for the sorted copy and the result list; only the last interval added to the result ever needs to be inspected or updated.

class Solution:
    def merge(self, intervals: list[list[int]]) -> list[list[int]]:
        intervals = sorted(intervals)
        res = [intervals[0]]
        for start, end in intervals[1:]:
            if start <= res[-1][1]:
                res[-1][1] = max(res[-1][1], end)
            else:
                res.append([start, end])
        return res


if __name__ == "__main__":
    print(Solution().merge([[1, 3], [2, 6], [8, 10], [15, 18]]))  # [[1,6],[8,10],[15,18]]
    print(Solution().merge([[1, 4], [4, 5]]))  # [[1,5]]
    print(Solution().merge([[4, 7], [1, 4]]))  # [[1,7]]
RecapThe whole problem in a few lines, for the night before
  • Spot it: a list of [start, end] ranges that need collapsing wherever two of them touch or overlap
  • Idea: sort by start value, then walk through once, extending the current group's end or starting a new one
  • Cost: O(n log n) time (the sort dominates), O(n) space (naive pairwise check: O(n²) time, O(n) space)
  • Trap: treating touching intervals (end == next start) as non-overlapping — they must still merge

Interview follow-ups

  • How would you merge one new interval into an already-merged, sorted list, without re-sorting everything?

    Binary search for where the new interval's start would fit among the existing intervals, since they're already sorted — that finds the range of existing intervals it might overlap with. Merge it with just that range (its neighbors before and after), splice the result back in, and the rest of the list never needs to move. This is the same idea as the optimal approach but narrowed to a small window instead of a full pass, so it costs O(log n) to locate the spot plus O(k) to merge the k intervals actually affected.

  • The intervals arrive continuously as a stream and you need the current merged state at any moment. What changes?

    You can't presort a stream, so maintain the result in a sorted structure (such as a balanced tree or sorted list) and, for each new interval, find its neighbors and merge in place the same way the "insert one interval" follow-up does. Each insertion costs roughly O(log n) to locate plus the cost of merging whatever it touches, which is far cheaper than resorting the whole collection every time a new interval shows up.

  • What if intervals could also specify a priority, and overlapping intervals should keep the higher-priority interval's boundaries instead of always taking the widest span?

    The overlap detection stays identical — sorting by start and scanning for touching intervals doesn't depend on any extra fields. What changes is what happens on a merge: instead of always taking max(end, otherEnd), you'd compare priorities and keep the higher-priority interval's start and end (or handle a tie some agreed way), potentially shrinking coverage instead of always growing it. The algorithm's structure and O(n log n) cost don't change, only the merge rule inside the loop.

Frequently asked questions

Anything with a start and an end that can pile up — maintenance windows, booked meeting rooms, firewall rule ranges, time-series gaps you want to collapse into fewer reports — turns into exactly this problem once you have more than a couple of them. Interviewers use it to check that you can turn a "looks messy" scheduling problem into a clean sort-and-scan.

Because the decision at each step is "does this interval's start fall inside the group I'm building" — that comparison only makes sense once you know intervals are visited in the order they begin. Sorting by end value would tell you which interval finishes first, which doesn't help you decide what to merge next.

It has to be <=. The problem treats two intervals that only touch, like [1,4] and [4,5], as overlapping — the shared boundary point is common to both. Using strict < would leave [1,4] and [4,5] as two separate results instead of merging them into [1,5].

It changes the cost, not the correctness: sorting an already-sorted list still costs the comparisons of a full sort unless the algorithm is told to skip it, so recognizing sorted input and skipping straight to the single pass turns the O(n log n) into O(n) overall. The single-pass merge logic itself doesn't change either way.