LeetCode 56 Merge Intervals Explained, Plus Insert Interval (57)

Merge Intervals is the entry point to a whole family of interval questions, and it shows up constantly in coding rounds because it tests three things in a few lines: whether you think to sort, whether you can state the overlap condition precisely, and whether you handle containment and touching endpoints. The code is short. The bugs are subtle.

This guide covers the sort-then-sweep solution with a proof of why it's correct, a dry run, code in three languages, the edge cases worth testing, Insert Interval as the natural follow-up, and a map of the related problems. For the whole family in one place, see the interval problems guide.

The Problem: Merge Overlapping Intervals

Given an array intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals and return an array of non-overlapping intervals that covers exactly the same points.

Constraints on LeetCode: 1 ≤ intervals.length ≤ 10⁴, and 0 ≤ start_i ≤ end_i ≤ 10⁴. So intervals are valid (start never exceeds end), there's at least one, and an O(n²) solution would be around 10⁸ operations, borderline. O(n log n) is the target.

When Do Two Intervals Overlap?

Get this condition exactly right before writing anything else. Two closed intervals [a, b] and [c, d] overlap if and only if:

The easiest way to remember it is through the negation. Two intervals don't overlap when one ends before the other starts: b < c or d < a. Negate that and you get the condition above.

Once intervals are sorted by start, we already know a ≤ c, so the first half of the condition is automatic and the test simplifies to just c ≤ b: the next interval starts no later than the current block ends.

The Sorting Approach and Why It Works

Brute force first

Without sorting, you could repeatedly scan all pairs, merge any two that overlap, and restart until nothing changes. That's O(n²) per pass and up to n passes, so O(n³) in the worst case. A cleaner brute force builds a graph where overlapping intervals are connected and merges each connected component (min start, max end), which is O(n²) for building edges. Both are worth one sentence in an interview to show you see why sorting helps.

The algorithm

1. Sort the intervals by start.
2. Open a block with the first interval.
3. For each next interval: if its start is ≤ the block's end, it overlaps, so set the block's end to max(blockEnd, intervalEnd). Otherwise the block is finished: append it to the output and open a new block with this interval.
4. Append the last block. (Or, as in the code below, keep the block as the last element of the output list so there's nothing to forget.)

Why it's correct

The key claim: when interval i starts after the current block ends, no later interval can overlap the current block. Every later interval j has start_j ≥ start_i > blockEnd, because the list is sorted by start. So the block is final and safe to output.

And when interval i does start within the block, merging is forced: the block covers start_i, so the union of the block and interval i is one contiguous range, from the block's start to the larger of the two ends. Because each merge only happens when it must, and each block is closed only when nothing later can touch it, the output is exactly the set of maximal merged ranges.

Why sort by start and not by end?

Sorting by end breaks the "no later interval can reach back" guarantee. Consider [[2,3],[4,5],[1,10]] sorted by end: [2,3], [4,5], [1,10]. A sweep would close [2,3] before seeing [1,10], which swallows everything. Sorting by end is the right tool for a different question, picking the most non-overlapping intervals (LeetCode 435), which is a greedy problem covered further down.

Dry Run on [[1,3],[8,10],[2,6],[15,18],[17,20]]

After sorting by start: [1,3], [2,6], [8,10], [15,18], [17,20].

Result: [[1,6],[8,10],[15,20]]. Now try the containment case [[1,10],[2,3],[4,5]]: at step 2, end becomes max(10, 3) = 10, not 3. If you wrote lastEnd = curEnd, the block would shrink to [1,3], and then [4,5] would be wrongly output as a separate block.

Merge Intervals Code in Python, C++ and Java

from typing import List

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda iv: iv[0])
        merged = []
        for start, end in intervals:
            if merged and start <= merged[-1][1]:
                merged[-1][1] = max(merged[-1][1], end)   # extend current block
            else:
                merged.append([start, end])              # start a new block
        return merged

Appending a fresh list [start, end] instead of the original interval object avoids mutating the caller's data when we later extend the end. It's a small thing, but aliasing bugs like this are what interviewers poke at.

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(),
             [](const vector<int>& a, const vector<int>& b) { return a[0] < b[0]; });
        vector<vector<int>> merged;
        for (const auto& cur : intervals) {
            if (!merged.empty() && cur[0] <= merged.back()[1]) {
                merged.back()[1] = max(merged.back()[1], cur[1]);
            } else {
                merged.push_back(cur);
            }
        }
        return merged;
    }
};

The default sort(intervals.begin(), intervals.end()) would also work because vectors compare lexicographically, but the explicit comparator states the intent and avoids comparing the second element needlessly.

import java.util.*;

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        List<int[]> merged = new ArrayList<>();
        for (int[] cur : intervals) {
            if (!merged.isEmpty() && cur[0] <= merged.get(merged.size() - 1)[1]) {
                int[] last = merged.get(merged.size() - 1);
                last[1] = Math.max(last[1], cur[1]);
            } else {
                merged.add(new int[] {cur[0], cur[1]});
            }
        }
        return merged.toArray(new int[merged.size()][]);
    }
}

Use Integer.compare(a[0], b[0]) rather than a[0] - b[0]. Subtraction overflows when values span close to the full int range (say, −2×10⁹ and 2×10⁹), which flips the sign and corrupts the sort. LeetCode's constraints are small enough that subtraction passes, but in an interview the safe version is the one to write. The Java Collections cheat sheet lists more of these comparator pitfalls.

In-place variant (O(1) extra beyond the sort)

def merge_in_place(intervals):
    intervals.sort(key=lambda iv: iv[0])
    w = 0                                   # index of the current block
    for i in range(1, len(intervals)):
        if intervals[i][0] <= intervals[w][1]:
            intervals[w][1] = max(intervals[w][1], intervals[i][1])
        else:
            w += 1
            intervals[w] = intervals[i]
    del intervals[w + 1:]
    return intervals

Complexity

Sorting space depends on the language: C++ std::sort is introsort with O(log n) recursion stack; Python's list.sort and Java's Arrays.sort on objects use TimSort, which can allocate up to O(n). If the interviewer asks for the space complexity, mention the sort explicitly instead of saying "O(1)". The sorting algorithms comparison has the details for each library.

Edge Cases Worth Testing

Note the "no overlaps" case: [1,2] and [3,4] do not merge even though they're adjacent integers, because the real-number range between 2 and 3 isn't covered. If the problem is about integer slots (seat numbers, for example), the interviewer may want them merged; that changes the condition to start ≤ lastEnd + 1.

Insert Interval (LeetCode 57)

You get a list of non-overlapping intervals already sorted by start, plus one newInterval. Insert it and merge as needed, keeping the list sorted and non-overlapping.

You could append and call your merge function: O(n log n). But the input is already sorted, so a linear pass does it. The intervals split into three groups relative to newInterval = [s, e]:

1. Entirely before: intervals with end < s. Copy them as is.
2. Overlapping: intervals with start ≤ e (and, since phase 1 passed them, end ≥ s). Absorb each one: s = min(s, start), e = max(e, end). Then append [s, e] once.
3. Entirely after: everything left. Copy as is.

from typing import List

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        result, i, n = [], 0, len(intervals)
        s, e = newInterval
        while i < n and intervals[i][1] < s:          # phase 1: before
            result.append(intervals[i])
            i += 1
        while i < n and intervals[i][0] <= e:         # phase 2: overlapping
            s = min(s, intervals[i][0])
            e = max(e, intervals[i][1])
            i += 1
        result.append([s, e])
        result.extend(intervals[i:])                  # phase 3: after
        return result

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> result;
        int i = 0, n = intervals.size();
        int s = newInterval[0], e = newInterval[1];
        while (i < n && intervals[i][1] < s) result.push_back(intervals[i++]);
        while (i < n && intervals[i][0] <= e) {
            s = min(s, intervals[i][0]);
            e = max(e, intervals[i][1]);
            ++i;
        }
        result.push_back({s, e});
        while (i < n) result.push_back(intervals[i++]);
        return result;
    }
};

Dry run

intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8].

Result: [[1,2],[3,10],[12,16]]. Edge cases: an empty intervals list (returns just the new interval), a new interval before everything, after everything, or swallowing everything. The three-phase code handles all of them without special cases, which is a good sign you've structured it right.

Can binary search make it faster?

You can binary-search the first interval with end ≥ s and the last with start ≤ e in O(log n) each. But building the output list is still O(n), so the total doesn't improve. It does help if the interval set lives in a mutable ordered structure (like a TreeMap) where you only delete the absorbed entries: then insertion is O(log n + k) for k absorbed intervals. That's the setup for LeetCode 352 (Data Stream as Disjoint Intervals) and 715 (Range Module).

Related Interval Problems and How They Differ

Once you can merge intervals, most of the family is a small change of sort key or loop body.

Meeting Rooms II: minimum rooms needed

This is the most common follow-up after Merge Intervals. Instead of merging, count the peak number of overlapping meetings. A neat O(n log n) way avoids heaps entirely: sort start times and end times separately, then sweep.

def min_meeting_rooms(intervals):
    starts = sorted(iv[0] for iv in intervals)
    ends = sorted(iv[1] for iv in intervals)
    rooms = best = 0
    j = 0
    for s in starts:
        while j < len(ends) and ends[j] <= s:   # half-open: a room freed at s is reusable
            rooms -= 1
            j += 1
        rooms += 1
        best = max(best, rooms)
    return best

# [[0,30],[5,10],[15,20]] -> 2

Notice the <= here treats meetings as half-open (a meeting ending at 10 frees the room for one starting at 10), the opposite convention from Merge Intervals. That contrast is a good thing to point out in an interview. The heap version, which keeps a min-heap of end times for the rooms in use, is covered in the heap and priority queue guide.

Non-overlapping Intervals: why it sorts by end

To remove the fewest intervals so the rest don't overlap, keep as many as possible. The greedy rule is to always keep the interval that finishes first, since it leaves the most room for the rest. That's the activity-selection problem, and the proof is an exchange argument covered in greedy algorithms: how to know when greedy works.

def erase_overlap_intervals(intervals):
    intervals.sort(key=lambda iv: iv[1])
    kept, last_end = 0, float('-inf')
    for s, e in intervals:
        if s >= last_end:            # touching is fine in LeetCode 435
            kept += 1
            last_end = e
    return len(intervals) - kept

Interval List Intersections (986)

def interval_intersection(A, B):
    i = j = 0
    out = []
    while i < len(A) and j < len(B):
        lo = max(A[i][0], B[j][0])
        hi = min(A[i][1], B[j][1])
        if lo <= hi:
            out.append([lo, hi])
        if A[i][1] < B[j][1]:        # the one ending first can't intersect anything else
            i += 1
        else:
            j += 1
    return out

How Merge Intervals Shows Up in Interviews

Interval questions are popular at product companies because they map to real systems: calendar free/busy views, booking slots, merging time ranges in log or metrics queries, and consolidating IP or ID ranges. An interviewer at a company like Razorpay or Swiggy might phrase it as "merge a merchant's settlement windows" or "find when at least one delivery partner was active", but it's the same problem.

What a strong answer includes

• Clarifications: Is the input sorted? Are endpoints inclusive? Can I modify the input? Can it be empty? Are values integers, and how large?
• The overlap condition stated precisely, before any code.
• A one-line correctness argument: "After sorting, if the next interval starts after the current end, nothing later can reach back."
• Self-tested edge cases: touching, nested, single interval.
• Accurate complexity, including the sort's memory.

Follow-ups to expect

• "Intervals arrive as a stream." Ordered map keyed by start; merge with floor/ceiling neighbours on each insert.
• "There are a billion intervals on disk." External merge sort by start, then a single streaming merge pass that needs only the current block in memory.
• "Return the total covered length." Merge, then sum end − start of each block.
• "Find the point covered by the most intervals." Sweep line: +1 at each start, −1 after each end, track the running maximum (this is Meeting Rooms II).
• "Merge only if the gap is at most k." Change the condition to start ≤ lastEnd + k.

If you can solve 56, 57, 253 and 435 cleanly and explain why one sorts by start and another by end, you've covered what most interviewers ask about intervals. For the broader array toolkit these sit inside, see array interview patterns.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.