## [435\. Non-overlapping Intervals](https://leetcode.com/problems/non-overlapping-intervals/)

Given an array of intervals `intervals` where `intervals[i] = [starti, endi]`, return _the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping_.

**Example 1:**

**Input:** intervals = \[\[1,2\],\[2,3\],\[3,4\],\[1,3\]\]
**Output:** 1
**Explanation:** \[1,3\] can be removed and the rest of the intervals are non-overlapping.

**Example 2:**

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

**Example 3:**

**Input:** intervals = \[\[1,2\],\[2,3\]\]
**Output:** 0
**Explanation:** You don't need to remove any of the intervals since they're already non-overlapping.

**Constraints:**

- `1 <= intervals.length <= 105`
- `intervals[i].length == 2`
- `-5 * 104 <= starti < endi <= 5 * 104`

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        // 先進行排序
        sort(intervals.begin(), intervals.end());
        int n = intervals.size();
        int res = 0;
        int lastEnd = intervals[0][1];
        for(int i = 1; i < n; i++) {
            int start = intervals[i][0];
            int end = intervals[i][1];
            if(start >= lastEnd) {
                lastEnd = end;
            } else {
                ++res;
                lastEnd = min(lastEnd, end);
            }
        }
        return res;
    }
};

:::success
- 時間複雜度：$O(N \cdot \log N)$
- 空間複雜度：$O(1)$
:::