Intervals - Merge Intervals

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

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

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

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.

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)