Interval problems

435. Non-overlapping Intervals

Actually, the problem is the same as “Given a collection of intervals, find the maximum number of intervals that are non-overlapping.” (the classic Greedy problem: Interval Scheduling). With the solution to that problem, guess how do we get the minimum number of intervals to remove? : )

Sorting Interval.end in ascending order is O(nlogn), then traverse intervals array to get the maximum number of non-overlapping intervals is O(n). Total is O(nlogn). From [1]

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        const int n = intervals.size();
        if (n == 0) return 0;
        sort(intervals.begin(), intervals.end(), [](vector<int> a, vector<int> b)
             {
                return a[1] < b[1]; 
             });
       
        int ret = 1;
        int end = intervals[0][1];
        for (int i = 1; i < n; ++i)
        {
            auto begin = intervals[i][0];
            if (begin >= end)
            {
                ret++;
                end = intervals[i][1];
            }
        }
        return n - ret;
    }
};

Reference

[1]https://leetcode.com/problems/non-overlapping-intervals/discuss/91713/Java:-Least-is-Most