Merge Intervals

1package pkg5leetcode;2 3/*4 * LeetCode 56: Merge Intervals  (Medium)5 * --------------------------------------6 * Merge all overlapping intervals.7 *8 * APPROACH: sort by start; merge when current start <= last merged end.9 * COMPLEXITY: Time O(n log n) (sort), Space O(n) for output.10 */11import java.util.*;12 13public class leetcode8MergeIntervals {14 15    static int[][] merge(int[][] intervals) {16        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));17        List<int[]> merged = new ArrayList<>();18        for (int[] cur : intervals) {19            if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < cur[0]) {20                merged.add(cur);                                   // no overlap21            } else {22                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], cur[1]);23            }24        }25        return merged.toArray(new int[0][]);26    }27 28    public static void main(String[] args) {29        int[][] r1 = merge(new int[][]{{1, 3}, {2, 6}, {8, 10}, {15, 18}});30        check(Arrays.deepEquals(r1, new int[][]{{1, 6}, {8, 10}, {15, 18}}), "overlap");31        int[][] r2 = merge(new int[][]{{1, 4}, {4, 5}});32        check(Arrays.deepEquals(r2, new int[][]{{1, 5}}), "touching");33        System.out.println("leetcode8MergeIntervals: all tests passed");34    }35 36    static void check(boolean cond, String name) {37        if (!cond) throw new AssertionError("FAILED: " + name);38        System.out.println("  PASS " + name);39    }40}