56. Merge Intervals

Math

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length <= 1) return intervals;

        // Step 1: Sort intervals by start time
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

        List<int[]> result = new ArrayList<>();

        // Step 2: Iterate through the intervals
        int[] current = intervals[0];
        result.add(current);

        for (int[] interval : intervals) {
            int currentEnd = current[1];
            int nextStart = interval[0];
            int nextEnd = interval[1];

            // If intervals overlap, merge them
            if (nextStart <= currentEnd) {
                current[1] = Math.max(currentEnd, nextEnd);
            } else {
                // Otherwise, move to next interval
                current = interval;
                result.add(current);
            }
        }

        return result.toArray(new int[result.size()][]);
    }
}

Remarks:

1. First sort, then combine intervals
2. Customize sort: Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
3. TC: $O(n \log n + n) = O(n \log n)$ ($n\log n$ is from sorting), SC: $O(n)$