Non-overlapping Intervals

Problem

Given an array of intervals intervals where intervals[i] = [start_i, end_i], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Note: Intervals are non-overlapping even if they have a common point. For example, [1, 3] and [2, 4] are overlapping, but [1, 2] and [2, 3] are non-overlapping.

Examples

Example 1:

Input: intervals = [[1,2],[2,4],[1,4]]

Output: 1

Explanation: After [1,4] is removed, the rest of the intervals are non-overlapping.

Example 2:

Input: intervals = [[1,2],[2,4]]

Output: 0

Constraints

• 1 <= intervals.length <= 1000
• intervals[i].length == 2
• -50000 <= starti < endi <= 50000

You should aim for a solution with O(nlogn) time and O(n) space, where n is the size of the input array.

Solution

Sort the intervals by starting value. We then iterate left-to-right. If the interval doesn’t intersect with the previous, we keep it. Otherwise need to remove one of the intervals, and we keep the one with the minimal end point as it has as lower chance of intersecting with more intervals to the right.

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        // Sort the intervals on the left interval size
        std::sort(intervals.begin(), intervals.end(), 
            [&](const auto &lhs, const auto &rhs) {
                return lhs[0] < rhs[0];
            }
        );
        int count = 0;
        int prev_end = intervals[0][1];
        for (int i = 1; i < intervals.size(); ++i) {
            int start = intervals[i][0];
            int end = intervals[i][1];
            // If start is current interval is right of prev
            //   we don't need to remove
            if (start >= prev_end) {
                prev_end = end;
            }
            // Otherwise, we need to remove the prev or this interval
            //  we keep the one which has the smallest end, as it has the
            //  lowest chance of covering more intervals
            else {
                ++count;
                prev_end = std::min(prev_end, end);
            }
        }
        return count;
    }
};

DP solution, but its O(n^2)

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [](const auto& a, const auto& b) {
            return a[0] < b[0];
        });
 
        int n = intervals.size();
        vector<int> memo(n, -1);
 
        int keep = dfs(intervals, 0, memo);
        return n - keep;
    }
 
private:
    int dfs(const vector<vector<int>>& intervals, int i, vector<int>& memo) {
        if (i >= intervals.size()) return 0;
        if (memo[i] != -1) return memo[i];
 
        // Option 1: remove/skip this interval
        int res = dfs(intervals, i + 1, memo);
 
        // Option 2: keep this interval, then continue from the next compatible one
        int j = i + 1;
        while (j < intervals.size() && intervals[j][0] < intervals[i][1]) {
            ++j;
        }
 
        res = max(res, 1 + dfs(intervals, j, memo));
        return memo[i] = res;
    }
};