LiveCodingInterview.com
← Articles

Merge Intervals: The Sort-and-Sweep Pattern Explained

Merge intervals is the pattern for taking a list of ranges, whether they're meeting times, date spans, or plain numeric bounds, and collapsing every pair that overlaps into the smallest set of ranges that still covers the same ground. The standard approach sorts the list by start value, then walks through once, extending the last merged range whenever the next interval touches it instead of comparing every interval against every other interval. Sorting does the expensive work, at O(n log n), and the single pass after it costs only O(n), so the whole thing beats the brute force pairwise comparison by a wide margin once the input gets past a handful of intervals. This guide covers the algorithm step by step with working code, the exact time and space complexity, the two follow-up variants interviewers actually ask (inserting one interval into an already-sorted list, and counting the minimum number of meeting rooms a schedule needs), and the mistakes that turn a correct idea into a wrong answer.

What Counts as an "Overlap" Between Two Intervals?

Two intervals overlap when one starts before or exactly when the other ends, so any shared point, even a single instant, counts. Given intervals [1, 3] and [2, 6], the second one starts at 2, which falls inside the first one's range, so they merge into [1, 6]. The condition to check is simple once you state it precisely: interval B overlaps interval A if B's start is less than or equal to A's end, assuming you've already sorted so A always starts no later than B.

The edge case that trips people up is a touching pair like [1, 4] and [4, 5], where one ends exactly where the next begins. Whether that counts as an overlap depends on what the intervals represent. Two meetings that share only the instant 4 usually don't conflict in a scheduling sense, but a numeric range problem asking you to merge [1, 4] and [4, 5] into [1, 5] almost always wants you to treat the shared endpoint as a merge. Read the problem statement for which convention it wants, and if it's ambiguous, say out loud which one you're assuming before you write a line of code.

How Do You Recognize a Merge Intervals Problem?

The signal is a list of ranges, each with a start and an end, where the question asks you to combine, count, or reason about overlaps rather than search for one specific value. Look for phrasing like "merge the overlapping intervals," "how many meetings conflict," "find the busiest time," or "insert this new range into the existing list." Anything involving calendar events, booking windows, or numeric ranges that might cover the same ground is a strong hint.

The pattern sits next to a few others that look similar on the surface but solve a different problem. If the question is about finding a value inside one sorted array, that's binary search, not this. If it's about scanning a contiguous run of an array or string for a property, sliding window fits better. Intervals are specifically about pairs of bounds representing ranges, and the fix is almost always some version of sort first, then sweep through once.

Why Doesn't Checking Every Pair of Intervals Work?

Checking every pair works, but it costs O(n squared) time, since each of the n intervals gets compared against every other interval, and that stops being fast once the list grows past a few hundred entries. The deeper problem isn't just speed. A pairwise approach also has to handle the case where merging interval A and interval C creates a new range that now overlaps interval B, which it hadn't touched on its own, so a naive pairwise pass can miss transitive merges unless you rerun it until nothing changes.

Sorting removes both problems at once. Once the intervals are ordered by start value, any interval that's going to merge with the current one has to appear immediately next to it in the sorted order, because nothing earlier could still be unmerged and nothing later could reach backward. That collapses the transitive-merge problem into a single forward pass, since each interval only ever needs to be compared against the most recently merged range instead of against every range that came before it.

How Does the Sort-and-Sweep Approach Work, Step by Step?

Sort the intervals by start value, then walk through them once, keeping a running "current merged range" that starts as the first interval. For each interval after that, check whether its start falls at or before the end of the current merged range. If it does, extend the current range's end to whichever is larger, the current end or the new interval's end. If it doesn't, the current range is finished, so push it into the result and start a new current range from this interval.

Trace it against [[1, 3], [2, 6], [8, 10], [15, 18]], which is already sorted by start value.

  1. Start with [1, 3] as the current merged range.
  2. Look at [2, 6], whose start, 2, is less than or equal to the current end, 3, so they overlap, and extend the current range's end to the larger of 3 and 6, giving [1, 6].
  3. Look at [8, 10], whose start, 8, is greater than the current end, 6, so it doesn't overlap, push [1, 6] into the result, and start a new current range at [8, 10].
  4. Look at [15, 18], whose start, 15, is greater than the current end, 10, so push [8, 10] into the result and start a new current range at [15, 18].
  5. No intervals remain, so push [15, 18] into the result.

The final answer is [[1, 6], [8, 10], [15, 18]], three ranges instead of the original four, with every overlap resolved in one pass over already-sorted data.

What Does the Code Look Like in Python?

The implementation mirrors the trace directly: sort once, then loop once, comparing each interval only against the last entry already in the result list.

def merge(intervals):
    if not intervals:
        return []

    intervals.sort(key=lambda pair: pair[0])
    merged = [intervals[0]]

    for start, end in intervals[1:]:
        last_start, last_end = merged[-1]
        if start <= last_end:
            merged[-1] = [last_start, max(last_end, end)]
        else:
            merged.append([start, end])

    return merged

The comparison, start less than or equal to last_end, is the entire overlap check from the walkthrough above. Everything else is bookkeeping: sort once up front, keep the result list as the running set of finished merged ranges, and mutate the last entry in place instead of allocating a new list every time two ranges combine.

What Is the Time and Space Complexity, Exactly?

Time complexity is O(n log n), and the sort is what sets that bound, since the merge pass itself only touches each interval once and does O(1) work per interval, which is O(n) on its own. Once you add the O(n log n) sort and the O(n) pass together, the sort term dominates for any list large enough to matter, so O(n log n) is the answer an interviewer expects.

Space complexity depends on what you count. The output list holds up to n intervals in the worst case, where nothing overlaps and every input interval survives untouched, which is O(n). Separately, Python's sort and most comparison sorts use O(log n) auxiliary space for the recursion or internal bookkeeping, on top of whatever the output costs. State both numbers if asked: O(n) for the result you have to return no matter what, and O(log n) on top of that for the sort itself, since collapsing them into a single vague "O(n)" answer skips a distinction some interviewers will probe on directly.

How Do You Solve Insert Interval Without Re-Sorting Everything?

Insert interval hands you a list that's already sorted and non-overlapping, plus one new interval to add, and asks for the result still sorted and non-overlapping. Re-sorting the whole list after appending the new interval works, but it throws away the fact that the input was already sorted, which is exactly the kind of shortcut an interviewer wants you to notice and use.

The faster approach walks the existing list once in three phases. First, copy every interval that ends strictly before the new interval starts, since those can never overlap it. Second, merge every interval that does overlap the new one into a single combined range, expanding the new interval's own start and end as you go, the same way the sweep in the main pattern does. Third, once you hit an interval that starts strictly after the (now expanded) new interval ends, insert the merged interval and copy the rest of the list unchanged.

def insert(intervals, new_interval):
    result = []
    i, n = 0, len(intervals)

    while i < n and intervals[i][1] < new_interval[0]:
        result.append(intervals[i])
        i += 1

    while i < n and intervals[i][0] <= new_interval[1]:
        new_interval = [
            min(new_interval[0], intervals[i][0]),
            max(new_interval[1], intervals[i][1]),
        ]
        i += 1

    result.append(new_interval)

    while i < n:
        result.append(intervals[i])
        i += 1

    return result

This runs in O(n) time with no sort at all, since the input was already ordered, which is the detail that separates a candidate who recognizes the shortcut from one who defaults to sorting out of habit.

How Do You Solve Meeting Rooms II With a Heap?

Meeting Rooms II asks for the minimum number of rooms needed to hold every meeting in a schedule without any two overlapping meetings sharing a room, and it needs a different tool than a plain sort-and-sweep because you're tracking how many rooms are in use at once, not merging ranges into fewer ranges.

Sort the meetings by start time, then use a min-heap that holds the end time of every meeting currently using a room. For each meeting, first check whether the room that frees up soonest, the smallest end time on the heap, is free before this meeting starts. If it is, pop that end time off the heap, since that room is now available. Then push the current meeting's end time onto the heap, whether or not a room was freed, because this meeting now occupies a room. The heap's size at the end, or its maximum size at any point during the loop, is the minimum number of rooms required.

import heapq

def min_meeting_rooms(intervals):
    if not intervals:
        return 0

    intervals.sort(key=lambda pair: pair[0])
    room_end_times = []

    for start, end in intervals:
        if room_end_times and room_end_times[0] <= start:
            heapq.heappop(room_end_times)
        heapq.heappush(room_end_times, end)

    return len(room_end_times)

This runs in O(n log n) time, driven by the sort and by the heap push and pop operations, each of which costs O(log n) and runs up to n times. It's a natural follow-up once you've solved the base merge intervals problem, since it reuses the same sort-by-start idea but swaps the merge step for a heap that tracks concurrent usage instead of combined ranges. Our guide to heap interview questions covers the min-heap mechanics this solution leans on in more depth, including the earlier-and-simpler Meeting Rooms question that only asks whether a conflict exists at all.

What Mistakes Cost Candidates Points on Interval Problems?

Forgetting to sort first is the most common one, and it's fatal, since the entire single-pass merge logic depends on the input already being ordered by start value. A candidate who writes the merge loop correctly but skips the sort will get a wrong answer on any input that isn't already sorted, and it often doesn't surface until the interviewer hands over a deliberately unsorted test case.

Getting the overlap condition backward is the second most common mistake, usually writing a strict less-than where the problem wants less-than-or-equal, or comparing the wrong pair of endpoints. Confirm out loud which convention the problem wants for touching intervals, [1, 4] and [4, 5] in particular, before you commit to strict or inclusive comparisons, since guessing wrong here produces an answer that's off by exactly one merge and is easy to miss in a quick self-check.

Mutating the input list while iterating over it is a subtler bug. Sorting in place before the loop starts is fine, but appending to or removing from the same list you're currently looping over inside the merge pass produces skipped elements or an index that no longer lines up with what you think it points to. Build a separate result list, as the code above does, and the problem doesn't come up.

The last one is forgetting the final interval. Since the merge loop only pushes the current range into the result once it hits an interval that doesn't overlap, the very last range being built never triggers that condition and has to be appended once the loop finishes. Skipping that line silently drops the last merged interval from the output, and it's the kind of bug that passes every test case except the one where the last two intervals in the input happen to overlap.

What Should You Say Out Loud While You Solve One?

Open by naming the pattern and the reason it applies: "this is asking me to combine overlapping ranges, so I'll sort by start value and sweep through once, since sorting turns a pairwise comparison problem into a single linear pass." That sentence tells the interviewer you recognized the shape of the problem before writing any code, rather than stumbling into the right approach by trial and error.

While you write the sort-and-sweep loop, narrate the overlap check as you write it, specifically which endpoints you're comparing and why, since that's the exact spot where an off-by-one mistake creeps in. Once the code is on the screen, trace it against a small example by hand, including one pair that overlaps and one that doesn't, and say the final complexity argument out loud: O(n log n) from the sort, O(n) space for the result, O(log n) extra for the sort itself if asked. If the interviewer follows up with insert interval or meeting rooms, say directly that it builds on the same sort-by-start idea before diving into the variant, since connecting the follow-up back to the base pattern is exactly the signal an interviewer is listening for.

Where Does Merge Intervals Fit Into Your Broader Pattern Prep?

Merge intervals belongs to the family of problems solved by sorting first and then making one pass, a group that also includes scheduling and greedy interval-selection questions, so the sort-then-sweep instinct you build here transfers directly. It differs from two pointers, which also depends on sorted input but moves two indices toward or across each other instead of extending a single running range, and from a monotonic stack, which tracks a different kind of ordering entirely, based on relative size rather than range overlap.

Our curated question bank pulls interval problems, including merge intervals, insert interval, and meeting rooms variants, from real candidate reports and onsite loops rather than a static public list, so what you practice matches what companies are actually asking right now. And if you want the full map of how this pattern relates to two pointers, sliding window, binary search, and the rest of the core set, our guide to spotting patterns before you code covers that signal-recognition habit across every pattern this site treats in depth.

Frequently Asked Questions

What is the merge intervals pattern used for in coding interviews?

It's used for any problem that hands you a list of ranges, meeting times, date spans, or numeric bounds, and asks you to combine the overlapping ones, count conflicts, or reason about coverage. The core technique, sort by start value and sweep through once, generalizes to a whole family of scheduling and interval questions beyond the basic merge.

Do the intervals need to be sorted before merging?

Yes, and this is the step candidates skip most often. The single-pass merge logic only works because sorting guarantees that any interval able to merge with the current one sits immediately next to it in the list. Skip the sort and the algorithm produces wrong answers on any input that wasn't already in order.

What is the time complexity of merge intervals?

O(n log n), set by the initial sort. The merge pass itself is O(n), touching each interval exactly once, but that gets dominated by the sort's O(n log n) once the list is large enough to matter. Space is O(n) for the result list, plus O(log n) of auxiliary space most comparison sorts use internally.

How is merge intervals different from insert interval?

Merge intervals starts from an unsorted list and needs a full sort before the sweep. Insert interval starts from a list that's already sorted and non-overlapping, with one new interval to fold in, so it skips the sort entirely and solves the problem in a single O(n) pass through the existing list.

Does merge intervals work with negative numbers or decimal values?

Yes, the algorithm only compares start and end values with less-than-or-equal and max, and neither operation cares whether the numbers are negative, fractional, or timestamps converted to integers. The same code handles [-5, -1] and [-3, 2] exactly as it handles any pair of positive integers.

What is the difference between Meeting Rooms and Meeting Rooms II?

Meeting Rooms asks a yes-or-no question, whether any two meetings in the schedule overlap at all, which you can answer by sorting and checking adjacent pairs. Meeting Rooms II asks how many rooms the schedule needs at minimum, which requires tracking how many meetings are running concurrently at any point, and that's what the min-heap of end times is for.