Share a dp approach, and not sure why the run time is still very good.


  • 0
    S

    I know many solutions use greedy approach, they are really good and simple. I came up with a more complicated dp approach, but surprisingly my dp approach beats 84% submissions and I am not sure why. Shouldn't the run time of my dp be O(n2)?

    Idea is from beginning to end, process one interval at a time. For interval i, if we erase it, then the number of erase would be dp[i-1] + 1. If we keep interval i, we need to check if interval i-1, i-2, ... are overlapping with interval i, and erase the overlapping intervals until we reach to interval i-x who is not overlapping with interval i. Then the number of erase would be dp[i-x] + # of erases from i-1 till i-x

    public int eraseOverlapIntervals(Interval[] intervals) {
            int n = intervals.length;
            if(n < 2){
                return 0;
            }
            
            Arrays.sort(intervals, new Comparator<Interval>(){
               public int compare(Interval a, Interval b){
                   return a.start == b.start? a.end - b.end : a.start - b.start;
               } 
            });
            
            //dp[i] means how many needs to be deleted from intervals 0 to i (both inclusive)
            int[] dp = new int[n];
            
            dp[0] = 0;
            
            for(int i = 1; i < n; i++){
                //if erase interval i
                int notKeepI = dp[i-1] + 1;
                //if keep interval i
                int left = i-1;
                while(left >=0 && intervals[left].end > intervals[i].start){
                    left --;
                }
                
                int keepI = i - left - 1 + (left >= 0 ? dp[left] : 0);
                dp[i] = Math.min(notKeepI, keepI);
            }
            
            return dp[n-1];
    
            
        }

Log in to reply
 

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