C++ DP solution


  • 0
    N

    This is not the better solution to the greedy solution (O(N^2)).
    The minimum number of intervals to erase can be computed from the maximum number of intervals that do not overlap.
    maximum number of intervals at ith position is
    the maximum between 1 (current interval) + maximum number of intervals at previous intervals that do not overlap11` and maximum number of intervals at i-1th interval.
    The algorithm computes this from bottom up.
    and the answer is number of intervals - maximum number of intervals at 0th entry.

     bool isSmaller(Interval& a, Interval& b)
     {
         if(a.start < b.start)
            return true;
        else 
            return false;
     }
     
    class Solution {
    public:
        int eraseOverlapIntervals(vector<Interval>& intervals) 
        {
            int sz = intervals.size();
            if(sz == 0)
                return 0;
                
            sort(intervals.begin(), intervals.end(), isSmaller);
            
            vector<int> tb(sz + 1, 0);
            
            tb[sz - 1] = 1;
            
            for(int i = sz - 2; i >= 0; i--)
           { 
                int candidateIdx = i + 1;
                //while overlap
                while(candidateIdx < tb.size() - 1 && 
                      intervals[i].end > intervals[candidateIdx].start && intervals[candidateIdx].end > intervals[i].start)
                {
                    candidateIdx++;
                }
                
                tb[i] = max(tb[candidateIdx] + 1, tb[i+1]);
            }
            
            return sz - tb[0];
        }
    };
    

Log in to reply
 

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