Non-overlapping Intervals

1package pkg5leetcode.blind75;2 3/*4 * Non-overlapping Intervals | LC 4355 * APPROACH: Greedy by earliest end time (activity selection).6 * COMPLEXITY: Time O(n log n), Space O(1)7 */8import java.util.*;9 10public class blind75_LC435NonOverlappingIntervals {11    static int eraseOverlapIntervals(int[][] intervals) {12        if (intervals.length == 0) return 0;13        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));14        int end = intervals[0][1], kept = 1;15        for (int i = 1; i < intervals.length; i++)16            if (intervals[i][0] >= end) { kept++; end = intervals[i][1]; }17        return intervals.length - kept;18    }19 20    public static void main(String[] args) {21        check(eraseOverlapIntervals(new int[][]{{1, 2}, {2, 3}, {3, 4}, {1, 3}}) == 1, "case1");22        check(eraseOverlapIntervals(new int[][]{{1, 2}, {1, 2}, {1, 2}}) == 2, "case2");23        System.out.println("all tests passed");24    }25 26    static void check(boolean cond, String name) {27        if (!cond) throw new AssertionError("FAILED: " + name);28        System.out.println("  PASS " + name);29    }30}