Merge Intervals

Problem Statement

Given a list of intervals [start, end], merge overlapping intervals into a minimal set of non-overlapping ones. This medium-level greedy problem is like tidying up a timeline—combine overlapping events into single blocks!

Example

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

Output: [[1,6],[8,10],[15,18]]

Input: intervals = [[1,4],[4,5]]

Output: [[1,5]]

Code

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

def merge(intervals):
    intervals.sort(key=lambda x: x[0])
    result = [intervals[0]]
    for i in range(1, len(intervals)):
        curr = result[-1]
        if curr[1] >= intervals[i][0]:
            curr[1] = max(curr[1], intervals[i][1])
        else:
            result.append(intervals[i])
    return result
            

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

Explanation

• Greedy Choice: Sort by start time, merge with the last interval if overlapping.
• Flow: Extend end time if overlap occurs; otherwise, add new interval.
• Example: [[1,3],[2,6]] → [1,6], then [8,10],[15,18] stay separate.

Note