Leetcode (435) - no overlapping interval

Leetcode（435）—— No overlap

subject

Given a set of intervals intervals , among intervals[i] = [starti, endi] . return The minimum number of intervals that need to be removed , Keep the remaining intervals from overlapping .

Example 1：

Input : intervals = [[1,2],[2,3],[3,4],[1,3]]
Output : 1
explain : remove [1,3] after , There's no overlap in the rest .

Example 2：

Input : intervals = [ [1,2], [1,2], [1,2] ]
Output : 2
explain : You need to remove two [1,2] So that the rest of the intervals don't overlap .

Example 3：

Input : intervals = [ [1,2], [2,3] ]
Output : 0
explain : You don't need to remove any intervals , Because they are already non overlapping .

Tips ：

• $1$ <= intervals.length <= $10^5$
• intervals[i].length == $2$
• $-5\ast 10^4$ <= starti < endi <= $5\ast 10^4$

Answer key

Method 1 ： Greedy Algorithm

Ideas

​​   We might as well think about which interval to choose as the first interval .

​​   Suppose in a certain The optimal In the selection method of ,$[l_k,r_k]$ It's the first （ That is, the leftmost ） Section , that There is no other section on its left , There are several non overlapping intervals on the right . imagine , If there is an interval $[l_j,r_j]$, bring $r_j<r_k$, That's the interval $j$ The right end of is in the interval $k$ The left side of the , So we will $k$ Replace with interval $j$, It does not overlap with the rest of the selected intervals on the right . And when we put the interval $k$ Replace with interval $j$ after , You get another kind of The optimal How to choose .

​​   We can constantly find the new area where the right end point is on the left of the right end point of the first interval , Replace the first interval with this interval . So when we can't replace , The first interval is the one with the smallest right endpoint among all the selectable intervals . So we sort all the intervals from small to large according to the right endpoint , Then the first interval after the sequence is arranged , Is the first interval we choose .

​​   When selecting the first interval , What if the right end points of multiple intervals are the same minimum ？ Because we chose the first interval , So there is no other section on its left , It doesn't matter where the left endpoint is , We just need to select an arbitrary interval with the smallest right endpoint .

​​   When the first interval is determined , All intervals that do not coincide with the first interval It makes up a Smaller subproblems . Because we have arranged all the intervals according to the right endpoint at the beginning , So for this sub problem , We don't have to sort again , as long as Find out the interval that does not coincide with the first interval and has the smallest right endpoint . In the same way , We can determine all subsequent intervals in turn .

​​   In actual code writing , We traverse the intervals ordered by the right endpoint , And maintain the right endpoint of the previous selection interval in real time $\text{right}$. If the currently traversed interval $[l_i,r_i]$ Does not coincide with the previous interval , namely $l_i\ge \text{right}$, Then we can greedily choose this range , And will $\text{right}$ Updated to $r_i$.

Code implementation

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

Complexity analysis

Time complexity ：$O(n\log n)$, among $n$ Is the number of intervals . We need to $O(n\log n)$ All intervals are sorted in ascending order according to the right endpoint , And need $O(n)$ Time to traverse . Because the former is greater than the latter in a progressive sense , So the total time complexity is $O(n\log n)$.
Spatial complexity ：$O(logn)$, This is the stack space needed for sorting .

Method 2 ： Dynamic programming

Ideas

​​   Because the requirements of the topic are equivalent to 「 Choose the largest number of intervals , So that they don't overlap 」. Since the selected intervals do not overlap , So we can sort them in descending order of endpoints , And whether we sort by left endpoint or right endpoint , The results are unique .
​​   thus , We can put all the $n$ The intervals are divided into left end points （ Or right endpoint ） Sort from small to large , Then the dynamic programming method is used to calculate the maximum number of intervals . Set this after the sequence is arranged $n$ The left and right endpoints of the two intervals are $l_0,\cdots ,l_{n-1}$ as well as $r_0,\cdots ,r_{n-1}$, Then we make $f_i$ Express 「 From the interval $0$ To the interval $i$ Of these intervals , The last interval is $i$ Under the circumstances , The maximum number of non overlapping intervals can be selected 」, The state transition equation is ：
$$f_i=\underset{j<i\wedge r_j\le l_i}{\max }\{f_j\}+1$$

​​   That is, we enumerate the number of the penultimate interval $j$, Satisfy $j<i$, And No $j$ The first interval must be the same as the $i$ The intervals do not overlap . Since we have sorted in ascending order by the left endpoint , So as long as the $j$ The right end of an interval $r_j$ Did not cross the $i$ The left end of an interval $l_i$, namely $r_j\le l_i$, So the first $j$ The first interval is the same as the $i$ The intervals do not overlap . We are in all that meet the requirements $j$ in , choice $f_j$ The largest one makes a state transition , If you can't find an interval that meets the requirements , So in the state transfer equation $\max$ This item is $0$,$f_i$ for $1$.
​​   The final answer is all $f_i$ Maximum of .

Code implementation

class Solution {
    
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    
        if (intervals.empty()) {
    
            return 0;
        }
        
        sort(intervals.begin(), intervals.end(), [](const auto& u, const auto& v) {
    
            return u[0] < v[0];
        });

        int n = intervals.size();
        vector<int> f(n, 1);
        for (int i = 1; i < n; ++i) {
    
            for (int j = 0; j < i; ++j) {
    
                if (intervals[j][1] <= intervals[i][0]) {
    
                    f[i] = max(f[i], f[j] + 1);
                }
            }
        }
        return n - *max_element(f.begin(), f.end());
    }
};

Complexity analysis

Time complexity ：$O(n^2)$, among $n$ Is the number of intervals . We need to $O(n\log n)$ All intervals are sorted in ascending order according to the left endpoint , And need $O(n^2)$ Time for dynamic planning . Because the former is smaller than the latter in the progressive sense , So the total time complexity is $O(n^2)$.
Note that method two is essentially a 「 Longest ascending subsequence 」 problem , So we can optimize the time complexity to $O(n\log n)$, For details, please refer to 「300. The official solution of the longest increasing subsequence 」.
Spatial complexity ：$O(n)$, That is to store all States $f_i$ The space needed .