java O(n^2) using DP [Accepted]


  • 2
    public class Solution {
        class myComparator implements Comparator<Interval> {
            public int compare(Interval a, Interval b) {
                return a.start - b.start;
            }
        }
        public boolean isOverlapping(Interval i, Interval j) {
            return i.end > j.start;
        }
        public int eraseOverlapIntervals(Interval[] intervals) {
            if (intervals.length == 0) {
                return 0;
            }
            Arrays.sort(intervals, new myComparator());
            int dp[] = new int[intervals.length];
            dp[0] = 1;
            int ans = 1;
            for (int i = 1; i < dp.length; i++) {
                int max = 0;
                for (int j = i - 1; j >= 0; j--) {
                    if (!isOverlapping(intervals[j], intervals[i])) {
                        max = Math.max(dp[j], max);
                    }
                }
                dp[i] = max + 1;
                ans = Math.max(ans, dp[i]);
    
            }
            return intervals.length - ans;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.