Insert Interval

1package pkg5leetcode.blind75;2 3/*4 * Insert Interval | LC 575 * APPROACH: Three phases: before, merge overlap, after new interval.6 * COMPLEXITY: Time O(n), Space O(n)7 */8import java.util.*;9 10public class blind75_LC57InsertInterval {11    static int[][] insert(int[][] intervals, int[] newInterval) {12        List<int[]> res = new ArrayList<>();13        int i = 0, n = intervals.length;14        while (i < n && intervals[i][1] < newInterval[0]) res.add(intervals[i++]);15        while (i < n && intervals[i][0] <= newInterval[1]) {16            newInterval[0] = Math.min(newInterval[0], intervals[i][0]);17            newInterval[1] = Math.max(newInterval[1], intervals[i][1]);18            i++;19        }20        res.add(newInterval);21        while (i < n) res.add(intervals[i++]);22        return res.toArray(new int[0][]);23    }24 25    public static void main(String[] args) {26        int[][] r = insert(new int[][]{{1, 3}, {6, 9}}, new int[]{2, 5});27        check(r.length == 2 && r[0][0] == 1 && r[0][1] == 5, "case1");28        int[][] r2 = insert(new int[][]{{1, 2}, {3, 5}, {6, 7}, {8, 10}, {12, 16}}, new int[]{4, 8});29        check(r2.length == 3 && r2[1][0] == 3 && r2[1][1] == 10, "case2");30        System.out.println("all tests passed");31    }32 33    static void check(boolean cond, String name) {34        if (!cond) throw new AssertionError("FAILED: " + name);35        System.out.println("  PASS " + name);36    }37}