JAVA dp solution (with explanation)


  • 0
    T

    Dynamic programming. Firstly we need to sort the intervals by their starting time in non-decreasing order.
    dp[k] refers to the minimum removing behaviors we need to carry out for the first k intervals.
    There are two possibilities for kth interval:
    1. Remove it: dp[k] = dp[k-1] + 1 (plus 1 means remove it)
    2. Keep it: The optimal solution is to remove every intervals which have overlapping area with kth element.
    We use j stands for the last element which doesn't overlap with kth element (j < k)
    dp[k] = dp[j] + (k-j-1) (plus (k-j-1) means move all overlapping intervals)

    /**
     * Definition for an interval.
     * public class Interval {
     *     int start;
     *     int end;
     *     Interval() { start = 0; end = 0; }
     *     Interval(int s, int e) { start = s; end = e; }
     * }
     */
    public class Solution {
        //Dynamic programming. Firstly we need to sort the intervals by their starting time in non-decreasing order.
        /*dp[k] refers to the minimum removing behaviors we need to carry out for the first k intervals.
        There are two possibilities for kth interval:
        1. Remove it: dp[k] = dp[k-1] + 1 (plus 1 means remove it)
        2. Keep it: The optimal solution is to remove every interval which has an overlapping area with kth element.
            We use j stands for the last element which doesn't overlap with kth element (j < k)
            dp[k] = dp[j] + (k-j-1) (plus (k-j-1) means move all overlapping intervals)
        */
        public int eraseOverlapIntervals(Interval[] intervals) {
            int[][] nums = new int[intervals.length+1][2];
            for(int i = 0; i < intervals.length; i++){
                nums[i][0] = intervals[i].start;
                nums[i][1] = intervals[i].end;
            }
            nums[intervals.length][0] = Integer.MIN_VALUE;
            nums[intervals.length][1] = Integer.MIN_VALUE;
            mergeSort(nums);
            int k = nums.length;
            int[] dp = new int[k];
            for(int i = 1; i < k; i++){
                int j = 0;
                for(j = i-1; j >=0; j--){
                    if(nums[i][0] >= nums[j][1]){
                        break;
                    }
                }
                int notTake = dp[i-1]+1;
                int take = dp[j]+i-j-1;
                dp[i] = Math.min(notTake, take);
            }
            return dp[k-1];
        }
        
        public static void mergeSort(int[][] nums){
    		if(nums.length>1){
    			//merge
    			int p = nums.length/2;
    			int[][] arr1 = new int[p][2];
    			int[][] arr2 = new int[nums.length-p][2];
    			for (int i = 0; i < p; i++) {
    				arr1[i][0] = nums[i][0];
    				arr1[i][1] = nums[i][1];
    			}
    			for (int i = p; i < nums.length; i++) {
    				arr2[i-p][0]=nums[i][0] ;
    				arr2[i-p][1]=nums[i][1] ;
    				
    			}
    			mergeSort(arr1);
    			mergeSort(arr2);
    			//sort
    			int m = 0,n=0;
    			for (int i = 0; i < nums.length; i++) {
    				if (m<arr1.length&&n<arr2.length&&arr1[m][1]<arr2[n][1]) {
    					nums[i][0]=arr1[m][0];
    					nums[i][1]=arr1[m][1];
    					m++;
    				}
    				else if (m<arr1.length&&n<arr2.length&&arr1[m][1]>=arr2[n][1]) {
    					nums[i][0]=arr2[n][0];
    					nums[i][1]=arr2[n][1];
    					n++;
    				}
    				else if (m>=arr1.length&&n<=arr2.length) {
    					nums[i][0]=arr2[n][0];
    					nums[i][1]=arr2[n][1];
    					n++;
    				}
    				else if (n>=arr2.length&&m<=arr1.length){
    					nums[i][0]=arr1[m][0];
    					nums[i][1]=arr1[m][1];
    					m++;
    				}
    			}
    			return;
    		}
    		else {
    			return;
    		}
    	}
    }
    

Log in to reply
 

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