53. Merge Intervals

Two intervals overlap iff one starts before the other ends. After sorting by start time, the only interval that can overlap the current one is the one we just placed in our output — a single comparison per step.

Approach

1. Sort intervals by their start.
2. Walk through the sorted list; maintain result with the last merged interval on top.
3. For the next interval [s, e]:
   • If s <= result[-1][1], extend: result[-1][1] = max(result[-1][1], e).
   • Else push a fresh interval [s, e].

Walk-through

[[1,3],[2,6],[8,10],[15,18]]

• sort → same.
• push [1,3].
• [2,6] overlaps (2 ≤ 3) → merge to [1,6].
• [8,10] starts after 6 → push.
• [15,18] starts after 10 → push.

Complexity

• Time: O(n log n) for the sort.
• Space: O(n) for the result.

import java.util.*;

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