Concise C++ Solution


  • 11
    class Solution {
    public:
        int eraseOverlapIntervals(vector<Interval>& intervals) {
            auto comp = [](const Interval& i1, const Interval& i2){ return i1.start < i2.start; };
            sort(intervals.begin(), intervals.end(), comp);
            int res = 0, pre = 0;
            for (int i = 1; i < intervals.size(); i++) {
                if (intervals[i].start < intervals[pre].end) {
                    res++;
                    if (intervals[i].end < intervals[pre].end) pre = i;
                }
                else pre = i;
            }
            return res;
        }
    };
    

  • 0
    S

    @zyoppy008 gggggoooodddddd


  • 0
    A

    @zyoppy008
    Can u please explain how we are using Greedy Approach in this question, using ur code?


  • 0
    N

    @abhihack03 the main idea is greedy, if we encounter two adjacent intervals overlap, we have to remove one of them, we remove the one that the tail is shortest (end is smaller)


  • 0
    D

    @zyoppy008 Very nice solution! I have a question for the syntax comp = {...}, why do we use [] here, does it have a special term in C++? Thanks.


  • 0
    I

    Good one @zyoppy008!


  • -1
    C

    Is the time complexity O(n)? Why didn't this post get more votes than the top voted one?


  • 0

    @coder2
    sort() function nlog(n)
    because I need you.


  • 0
    P

    @newtt I think if there emerge a duplicate, we should delete the one with bigger tail, because that one has more chance to be duplicate with the following intervals.
    So is the logic in the above code, you should read that again :)


  • 0
    W

    I have the same Idea.
    This problem is similar to 452. Minimum Number of Arrows to Burst Balloons
    I using one variable to record the former end

    class Solution {
        struct CMP {
            bool operator () (const Interval &a, const Interval &b) {
                if (a.end == b.end) {
                    return a.start > b.start;
                }
                return a.end < b.end;
            }
        }cmp;
    public:
        int eraseOverlapIntervals(vector<Interval>& intervals) {
            int ans = 0, pre_r = INT_MIN;
            sort(intervals.begin(), intervals.end(), cmp);
            for (int i = 0; i < intervals.size(); i++) {
                if (intervals[i].start < pre_r) {
                    ans++;
                } else {
                    pre_r = intervals[i].end;
                }
            }
            return ans;
        }
    };
    

  • 0
    J

    I got the same idea. Actually, the answer for the problem is :
    Intervals.size - the answer for "minimum arrows to burst ballons"
    Only one thing to be care: In that problem, we admit "touching" as overlapping, but here we say no.


  • 0
    A

    @JadenPan I kind of think this problem and the minimum arrows to burst ballons is somehow relative to each other, but I can't figure out how. Would you explain a bit why Intervals.size - the answer for "minimum arrows to burst ballons" is the answer?


  • 0
    H
    int eraseOverlapIntervals(vector<Interval>& intervals) {
            int count = 0;
            if(intervals.empty()) return count;
            
            auto compare = [](Interval a, Interval b) {return a.end < b.end;};
            sort(intervals.begin(), intervals.end(), compare);
            
            Interval pre = intervals[0];
            for(int i = 1; i < intervals.size(); i++)
                if(intervals[i].start < pre.end) 
                    {count++; continue;}     
                else
                    pre = intervals[i];
            
            return count;
        }

  • 0
    S

    @zyoppy008 very nice solution!


Log in to reply
 

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