Non-overlapping Intervals -- LeetCode 435

[Question]

Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Note:

1. You may assume the interval's end point is always bigger than its start point.
2. Intervals like [1,2] and [2,3] have borders "touching" but they don't overlap each other.

Example 1:

Input: [ [1,2], [2,3], [3,4], [1,3] ]

Output: 1

Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.

Example 2:

Input: [ [1,2], [1,2], [1,2] ]

Output: 2

Explanation: You need to remove two [1,2] to make the rest of intervals non-overlapping.

Example 3:

Input: [ [1,2], [2,3] ]

Output: 0

Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

[Analysis]
This problem is equivalent to the problem "Minimum Number of Arrows to Burst Balloons". Instead of counting the overlapping intervals, this problem needs to calculate the number of redundant intervals.

The basic idea is to use a greedy approach. 1) sort the intervals by the ends; 2) suppose we have a few selected non-overlapping intervals, use the end of  the last interval X as a vertical scan line from left to right: any intervals with start that is smaller than the scan line will be overlapped with X, therefore, place the first non-overlapping interval X1 into selected list and repeat 2).

[Solution]
class Solution {
public:
    int eraseOverlapIntervals(vector<Interval>& intervals) {
        auto comp = [](Interval a, Interval b) { return a.end==b.end && a.start<b.start|| a.end<b.end;};
        sort(intervals.begin(), intervals.end(), comp);
     
        int count=0, line = INT_MIN;
        for(auto& e: intervals) {
            if (e.start< line ) continue;
            count++;
            line = e.end;
        }
        return intervals.size()-count;
    }
};