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

• 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];

}``````

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