Skip to main content

1.3 Interval Problem

435. Non-overlapping Intervals​

Problem Description​

Given multiple intervals, calculate the minimum number of intervals that need to be removed to make the remaining intervals non-overlapping. Adjacent intervals that meet at endpoints are not considered overlapping.

Input and Output Example​

The input is an array containing multiple subarrays, each with a fixed length of 2, representing the start and end of each interval. The output is an integer indicating the number of intervals that need to be removed.

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

In this example, we can remove the interval [1,3] so that the remaining intervals [[1,2], [2,4]] are non-overlapping.

Solution Explanation​

Finding the minimum number of intervals to remove is equivalent to maximizing the number of non-overlapping intervals we can retain. When selecting intervals to keep, the end point of each interval is critical: the smaller the chosen interval’s end, the more space is left for other intervals, allowing more intervals to be retained. Thus, the greedy strategy we use is to prioritize retaining intervals with smaller end points that do not overlap.

The specific implementation involves first sorting the intervals in ascending order by their end points (using a lambda function) and then selecting the interval with the smallest end point that does not overlap with the previously chosen interval.

In the example, the sorted array is [[1,2], [1,3], [2,4]]. According to our greedy strategy, we initialize with the interval [1,2]; since [1,3] overlaps with [1,2], we skip this interval; since [2,4] does not overlap with [1,2], we keep it. Therefore, the final retained intervals are [[1,2], [2,4]].

warning

It is necessary to determine whether to sort by the start or end of the intervals based on the specific requirements.

int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end(),
         [](vector<int>& a, vector<int>& b) { return a[1] < b[1]; });
    int removed = 0, prev_end = intervals[0][1];
    for (int i = 1; i < intervals.size(); ++i) {
        if (intervals[i][0] < prev_end) {
            ++removed;
        } else {
            prev_end = intervals[i][1];
        }
    }
    return removed;
}