Merge Intervals — Sort + Linear Scan O(n log n) [Google, Meta, Amazon]

Problem Statement

Given an array of intervals, merge all overlapping intervals and return non-overlapping intervals.

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

Intuition
C++ Solution
Java Solution
Python Solution
JavaScript Solution
Complexity: O(n log n) sort, O(n) scan, O(n) space

Intuition

Sort by start time. Walk left to right. If current interval's start ≤ last merged interval's end → they overlap, extend the end. Otherwise push the new interval.

C++ Solution

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

Java Solution

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

Python Solution

def merge(intervals):
    intervals.sort()
    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

JavaScript Solution

function merge(intervals) {
    intervals.sort((a,b)=>a[0]-b[0]);
    const res = [intervals[0]];
    for (let i = 1; i < intervals.length; i++) {
        const last = res[res.length-1];
        if (intervals[i][0] <= last[1])
            last[1] = Math.max(last[1], intervals[i][1]);
        else
            res.push(intervals[i]);
    }
    return res;
}