Merge Intervals

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

Example 1

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

Example 2

Input: [[1,4],[4,5]] → Output: [[1,5]]

Solution Approach

Sort by start time. Iterate: if current interval overlaps with last merged interval, expand it. Otherwise, add to result.

Sort intervals by start.
Initialize result with first interval.
For each subsequent interval: if its start <= last.end, expand last.end = max(last.end, curr.end).
Else add current interval to result.

Java

import java.util.*;

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[] curr : intervals) {
            int[] last = res.get(res.size() - 1);
            if (curr[0] <= last[1]) last[1] = Math.max(last[1], curr[1]);
            else res.add(curr);
        }
        return res.toArray(new int[0][]);
    }
}

Time Complexity: O(N log N)
Space Complexity: O(N)