December 28, 2019

435. Non-overlapping Intervals

Sol 1. DP (Not optimal)

Time = O(n^2), Space = O(n)

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) {
            return 0;
        }
        Arrays.sort(intervals, new Comparator<int[]>(){
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] != o2[0] ? o1[0] - o2[0]: o1[1] - o2[1];
            }
        });
        int[] count = new int[intervals.length];
        count[0] = 1;
        for (int i = 1; i < intervals.length; i++) {
            for (int j = 0; j < i; j++) {
                if (intervals[j][1] <= intervals[i][0]) {
                    count[i] = Math.max(count[i], count[j] + 1);
                } 
            }
            count[i] = Math.max(count[i], 1);
        }
        return intervals.length - count[intervals.length - 1];
    }
}

Sol 2. Greedy

Refer to this post
See wiki of Interval Scheduling Maximization

Greedy polynomial solution The following greedy algorithm does find the optimal solution:

Select the interval, x, with the earliest finishing time.

Remove x, and all intervals intersecting x, from the set of candidate intervals.

Repeat until the set of candidate intervals is empty.

The trick here is to **sort by end time **.

Similar questions:

Time = O(nlogn), Space = O(1)

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) {
            return 0;
        }
        Arrays.sort(intervals, new Comparator<int[]>(){
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1]; // sort by end time
            }
        });
        int count = 1;
        int[] preInterval = intervals[0];
        for (int i = 1; i < intervals.length; i++) {
            if (preInterval[1] <= intervals[i][0]) {
                preInterval = intervals[i];
                count ++;
            }
        }
        return intervals.length - count;
    }
}