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;
}
};
Concise C++ Solution



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

@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)

@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.



@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 :)

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 endclass 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; } };

@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 whyIntervals.size  the answer for "minimum arrows to burst ballons"
is the answer?

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