Merge Intervals: Optimal Solution (Data-Backed Guide)

The Data: Why This Gets Asked at Top Companies

Merge Intervals is a favourite at companies that work with scheduling, calendars, time-series data, and resource allocation — which is nearly every major tech company.

Notice the spread: FAANG, finance (Goldman, Citadel, J.P. Morgan, Morgan Stanley), and product companies (Dropbox, LinkedIn, Expedia) all ask this. The underlying reason: interval merging shows up naturally in calendar apps, meeting schedulers, log processors, and resource managers — real engineering problems these companies deal with daily.

Problem Statement

LeetCode #56 — Merge Intervals

Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.

Input:  intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: [1,3] and [2,6] overlap → merge to [1,6].

Input:  intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: [1,4] and [4,5] touch at 4 → merge to [1,5].

Input:  intervals = [[1,4],[0,4]]
Output: [[0,4]]
Explanation: After sorting: [0,4] and [1,4] → merge to [0,4].

The Core Intuition: Why Sort First?

The key question is: why does sorting make this problem easy?

Without sorting, any interval could potentially overlap with any other. You'd have to compare every pair — O(n²). But once you sort by start time, a crucial property emerges: if interval A and interval C don't overlap (A ends before C starts), then no interval between them in sorted order can overlap with A either.

This means you only ever need to compare the current interval with the last interval in your result list. You never need to look further back. That's what makes a single greedy pass possible after sorting.

The Algorithm: Sort + Greedy Merge

1. Sort all intervals by their start time.
2. Initialize result list with the first interval.
3. Iterate through remaining intervals. For each interval:
   • If it overlaps with the last interval in result (current.start <= last.end) → merge by updating last.end = max(last.end, current.end)
   • If it doesn't overlap → append it to result as a new interval
4. Return the result list.

Visual Walkthrough

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

Code in Python, Java & JavaScript

def merge(intervals: list[list[int]]) -> list[list[int]]:
    # Sort by start time
    intervals.sort(key=lambda x: x[0])

    merged = [intervals[0]]

    for current in intervals[1:]:
        last = merged[-1]

        if current[0] <= last[1]:
            # Overlap — extend the end if needed
            last[1] = max(last[1], current[1])
        else:
            # No overlap — start a new interval
            merged.append(current)

    return merged

class Solution {
    public int[][] merge(int[][] intervals) {
        // Sort by start time
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

        List<int[]> merged = new ArrayList<>();
        merged.add(intervals[0]);

        for (int i = 1; i < intervals.length; i++) {
            int[] last = merged.get(merged.size() - 1);
            int[] current = intervals[i];

            if (current[0] <= last[1]) {
                // Overlap — extend the end
                last[1] = Math.max(last[1], current[1]);
            } else {
                // No overlap — add new interval
                merged.add(current);
            }
        }

        return merged.toArray(new int[merged.size()][]);
    }
}

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function(intervals) {
    // Sort by start time
    intervals.sort((a, b) => a[0] - b[0]);

    const merged = [intervals[0]];

    for (let i = 1; i < intervals.length; i++) {
        const last = merged[merged.length - 1];
        const current = intervals[i];

        if (current[0] <= last[1]) {
            // Overlap — extend the end
            last[1] = Math.max(last[1], current[1]);
        } else {
            // No overlap — add new interval
            merged.push(current);
        }
    }

    return merged;
};

Complexity Analysis

Interview-ready explanation: "We sort in O(n log n) then do a single O(n) greedy pass. Overall time is O(n log n). Space is O(n) for the output — or O(log n) if we don't count output space and the sort is in-place."

Interval Problem Family: 5 Must-Know Variants

Merge Intervals is the gateway to an entire family of interval problems. Interviewers at Google, Amazon, and Bloomberg regularly follow up with these variants.

Variant 1: Insert Interval (LeetCode #57)

"Given a sorted list of non-overlapping intervals and a new interval, insert it and merge if necessary."

Insight: Walk through in three phases — add all intervals ending before the new one starts, merge all overlapping intervals with the new one, then add the rest. O(n) time — no sort needed since input is already sorted.

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

    # Phase 1: add all intervals ending before newInterval starts
    while i < n and intervals[i][1] < newInterval[0]:
        result.append(intervals[i])
        i += 1

    # Phase 2: merge all overlapping intervals
    while i < n and intervals[i][0] <= newInterval[1]:
        newInterval[0] = min(newInterval[0], intervals[i][0])
        newInterval[1] = max(newInterval[1], intervals[i][1])
        i += 1
    result.append(newInterval)

    # Phase 3: add remaining intervals
    while i < n:
        result.append(intervals[i])
        i += 1

    return result

Variant 2: Non-Overlapping Intervals (LeetCode #435)

"Find the minimum number of intervals to remove to make the rest non-overlapping."

Insight: Sort by end time (not start). Greedily keep the interval that ends earliest — this leaves the most room for future intervals. Count how many you must skip. O(n log n).

Variant 3: Meeting Rooms I (LeetCode #252)

"Given meeting time intervals, can a person attend all meetings?"

Insight: Sort by start time. If any meeting starts before the previous one ends, return false. O(n log n).

Variant 4: Meeting Rooms II (LeetCode #253)

"Find the minimum number of conference rooms required."

Insight: Use a min-heap of end times. For each new meeting, if the earliest-ending meeting is done, reuse that room. Otherwise open a new room. Heap size = minimum rooms needed.

import heapq

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

    intervals.sort(key=lambda x: x[0])
    heap = []  # min-heap of end times

    for start, end in intervals:
        if heap and heap[0] <= start:
            heapq.heapreplace(heap, end)  # reuse room
        else:
            heapq.heappush(heap, end)     # open new room

    return len(heap)

Variant 5: Employee Free Time (LeetCode #759)

"Given schedules of all employees, find the free time intervals common to all."

Insight: Flatten all intervals, sort, merge overlapping ones (same as #56), then collect the gaps between consecutive merged intervals.

The Bigger Pattern: When Intervals Appear

The sort-and-scan interval pattern signals itself with specific keywords. Train yourself to recognize them immediately.

• "Overlapping" — sort by start, scan with a running interval in a result list
• "Meeting rooms" / "schedules" — sort by start + min-heap to track concurrent events
• "Minimum removals" — sort by end time, greedily keep earliest-ending interval
• "Free time" / "gaps" — merge first, then collect spaces between merged intervals
• "Insert and merge" — three-phase walk: before, overlap, after

How to Actually Remember This

With 127 appearances at 47 companies — including every major FAANG and finance firm — you will see an interval problem in a serious interview. The sort-then-merge pattern is mechanical once internalized, but it requires practice to execute cleanly under pressure.

Tag all 6 interval problems together on DSAPrep.dev under Intervals and Sorting. The spaced repetition system groups related problems and surfaces them together — so reviewing one reinforces the whole family.

One problem at a time. One review at a time. Future you will thank present you.