Merge Intervals

1package pkg5leetcode.blind75;2 3/*4 * Merge Intervals | LC 565 * APPROACH: Sort by start; merge if overlap else push.6 * COMPLEXITY: Time O(n log n), Space O(n)7 */8import java.util.*;9 10public class blind75_LC56MergeIntervals {11    static int[][] merge(int[][] intervals) {12        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));13        List<int[]> res = new ArrayList<>();14        for (int[] iv : intervals) {15            if (res.isEmpty() || res.get(res.size() - 1)[1] < iv[0]) res.add(iv);16            else res.get(res.size() - 1)[1] = Math.max(res.get(res.size() - 1)[1], iv[1]);17        }18        return res.toArray(new int[0][]);19    }20 21    public static void main(String[] args) {22        int[][] r = merge(new int[][]{{1, 3}, {2, 6}, {8, 10}, {15, 18}});23        check(r.length == 3 && r[0][1] == 6, "case1");24        int[][] r2 = merge(new int[][]{{1, 4}, {4, 5}});25        check(r2.length == 1 && r2[0][1] == 5, "case2");26        System.out.println("all tests passed");27    }28 29    static void check(boolean cond, String name) {30        if (!cond) throw new AssertionError("FAILED: " + name);31        System.out.println("  PASS " + name);32    }33}