Why can't we remove the most overlapping intervals?


  • 1

    It's easy to think that:

    • If we count the overlapping times with each interval.
    • Then, for each time we remove the interval with most overlapping interval(let's call it A)
    • And we update the other intervals' overlapping time which is overlapped with A.
    • When all interval has zero overlapping times, we get the result.

    I know how to do it in greedy in O(nlgn) time, but I wonder why this cant work...
    This idea failed in the last test case(that with 10k inputs).I can't figure out why... Can someone help me?please...?
    Thanks your time for seeing these. Thank you~


  • 1

    If I come up with a counterexample to the strategy, I'd like to be able to actually test it... but I need code for that. Also, how do you know it's your strategy that's faulty, not your implementation of it? Again it would be helpful to see code.

    Edit: Again, I'd really really like to actually double-check with the code, but here's a counterexample for the strategy as I understand it: [0,2],[1,3],[2,4],[3,5],[4,6]. You might remove [2,4], which is wrong.


  • 0

    @StefanPochmann
    Hey it's you again! You're so great!
    This is my implementation, a little bit too long..Hope this won't brother you...

    class Solution {
    public:
        int eraseOverlapIntervals(vector<Interval>& intervals) {
            const int len=intervals.size();
            if(len==0)
                return 0;
            sort(intervals.begin(),intervals.end(),cmp);
            //overlapping times for each interals
            int overlaps[len]={0};
            //counter is the total overlapping times; res is the min intervals to remove
            int counter=0,res=0;
            for(int i=0;i<len;++i){
                for(int j=i+1;j<len;++j){
                    if(intervals[j].start>=intervals[i].end)
                        break;
                    else{
                        ++overlaps[i];
                        ++overlaps[j];
                        counter+=2;
                    }
                }
            }
            while(counter){
                int maxv=0,maxi=-1;
                for(int i=0;i<len;++i){
                    if(overlaps[i]>maxv){
                        maxi=i;
                        maxv=overlaps[maxi];
                    }
                }
                counter-=overlaps[maxi];
                overlaps[maxi]=0;
                ++res;
                int left=maxi-1,right=maxi+1;
                while(left>=0){
                    if(intervals[left].end>intervals[maxi].start && overlaps[left]>0){
                        --overlaps[left];
                        --counter;
                    }
                    --left;
                }
                while(right<len && intervals[right].start<intervals[maxi].end){
                    if(overlaps[right]>0){
                        --overlaps[right];
                        --counter;
                    }
                    ++right;
                }
            }
            return res;
        }
    private:
        static bool cmp(Interval &lhs,Interval &rhs){
            return lhs.start==rhs.start?(lhs.end<rhs.end):(lhs.start<rhs.start);
        }
    };
    

  • 1

    @HelloKenLee The code length doesn't bother me because I'm not reading it :-). At least not unless I have to. But I didn't have to. Well, it survived the counterexample to your strategy I mentioned above. I even tried all 120 permutations of those five intervals, but your code got all of them right. I guess somehow it avoids removing [2,4] by using another criterion not described in your strategy. Anyway... I then instead forced it to remove [2,4] by duplicating the actual bad intervals, so that [2,4] is the only interval with highest overlapping count. For input [[0,2],[1,3],[1,3],[2,4],[3,5],[3,5],[4,6]], your code returns 5, while the correct answer is 4.

    Edit: Ahaha, actually I should've had a quick look at your code. Now that I did, I see the first thing you do is sort the intervals, so my testing of all permutations was pointless :-)


  • 0

    @StefanPochmann
    Yeah... I also shrink the final test case to [[-7,76], [58,64],[66,87],[76,127],[78102],[88,112]], and it went wrong...But I cant find out what was wrong in the algorithm(or implementation)... can you tell me why? Anyway, thank you for your valuable time, really~

    UPDATED: the test case should be: [[-7,76],[58,64],[66,87],[76,127],[78,102],[88,112]]


  • 0
    A

    @HelloKenLee I think the pitfall was that the first interval was removed when there are multiple intervals with the same overlapping times. You can try to remove the one with the largest ending.

    BTW, there is a comma missing in your test case. It should be [[-7,76],[58,64],[66,87],[76,127],[78,102],[88,112]].

                for(int i=0;i<len;++i){
                    if(overlaps[i]==maxv && intervals[i].end > intervals[maxi].end){
                        maxi=i;
                        maxv=overlaps[maxi];
                    }
                    else if(overlaps[i]>maxv){
                        maxi=i;
                        maxv=overlaps[maxi];
                    }
                }
    

  • 0

    @Alpher
    Oh! My bad, corrected now. Anyway, did that code you comment pass all the test case?


  • 0
    A

    @Alpher I agree that the bug is when there are more than one maxv.
    But always choosing the one with the rightmost end among the same maxv would not work, because that is basically choosing the last one instead of the first one. I suspect it would still fail certain testcases.

    E.g. Consider the same testcase but left-right flipped (as if looking from right to left).


Log in to reply
 

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