Merge Intervals — Sort and Sweep

Merge Intervals shows up everywhere — calendar systems, log compaction, range queries, even garbage collection. The problem is simple to state: given a list of intervals, merge any that overlap. The trick is in spotting that sorting transforms a quadratic problem into a linear one.

The Problem

You are given an array of intervals where intervals[i] = [start_i, end_i]. Return an array of non-overlapping intervals that cover all the input intervals.

Example: [[1,3],[2,6],[8,10],[15,18]] becomes [[1,6],[8,10],[15,18]] because [1,3] and [2,6] overlap.

Intuition

The naive idea is to repeatedly scan the list, find any overlapping pair, merge them, and restart. That works but it is O(n^2) at minimum, and the “restart after every merge” logic is annoying to write correctly.

The key insight: if we sort intervals by their start, then any overlap must be with the previous interval in the sorted order. Why? Because every later interval starts at or after the current one, so once a gap appears, every future interval also starts past that gap. That collapses the problem into a single pass: keep a merged list, and for each new interval either extend the last merged interval’s end or append a new one.

The condition start <= last_end is inclusive on purpose. The standard problem treats [1,4] and [4,5] as overlapping because they share the endpoint 4. If the prompt says “touching is fine, only merge strict overlaps,” use strict <. Always confirm this with the interviewer.

Explanation with Example

Input: [[1,3],[2,6],[8,10],[15,18]] (already sorted by start).

1. merged = [[1,3]].
2. [2,6]: 2 <= 3, so merge. merged = [[1,6]].
3. [8,10]: 8 > 6, append. merged = [[1,6],[8,10]].
4. [15,18]: 15 > 10, append. Final: [[1,6],[8,10],[15,18]].

number line:
 1   2   3   4   5   6   7   8   9  10        15      18
 |---|---|                                                  [1,3]
     |---|---|---|---|                                      [2,6]
                             |---|---|                      [8,10]
                                                |---...--|  [15,18]

after sweep (overlapping with previous merges):
 |---------------|         |---|             |---------|
 [    1 , 6     ]         [8,10]            [   15,18  ]

merged = [ [1,3] ]
next = [2,6]    2 <= 3  -> merge   last[1] = max(3,6) = 6
merged = [ [1,6] ]
next = [8,10]   8 >  6  -> append
merged = [ [1,6], [8,10] ]
next = [15,18] 15 > 10  -> append
merged = [ [1,6], [8,10], [15,18] ]

Code

def merge(intervals):
    if not intervals:
        return []
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0][:]]
    for start, end in intervals[1:]:
        last = merged[-1]
        if start <= last[1]:
            last[1] = max(last[1], end)
        else:
            merged.append([start, end])
    return merged

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

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

Edge Cases

• Empty input: return [].
• Single interval: return a copy of it.
• Already sorted, no overlaps: should pass through unchanged.
• All intervals collapse into one: [[1,10],[2,3],[4,5]] becomes [[1,10]].
• Intervals fully contained inside others: covered automatically by max(last_end, end).
• Negative coordinates: the algorithm does not care; it only compares values.

Complexity Analysis

• Sort: O(n log n).
• Sweep: O(n).
• Total: O(n log n). Space is O(n) for the output, or O(log n) auxiliary for the sort’s stack if the output is not counted.

How to Explain It in an Interview

State the sort idea explicitly, handle the inclusive endpoint correctly, write the sweep without off-by-one bugs, and name at least two edge cases unprompted. Bonus points for mentioning that the sort is the bottleneck, so if intervals were already sorted, the whole thing is O(n).

Related Problems

• Insert Interval: same merge logic, but insert into an already-sorted list in O(n).
• Meeting Rooms: check whether any two intervals overlap after sorting.
• Employee Free Time: merge across multiple sorted lists, then take the gaps.

Wrap up

Master this pattern and you unlock at least a dozen related problems with almost no extra thinking.