JAVA dp solution (with explanation)

• 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;
}
}
}
``````

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