?LeetCode刷題實(shí)戰(zhàn)435：無重疊區(qū)間

示例 1:

輸入: [ [1,2], [2,3], [3,4], [1,3]?]
輸出: 1
解釋: 移除 [1,3]?后，剩下的區(qū)間沒有重疊。

示例 2:

輸入: [ [1,2], [1,2], [1,2]?]
輸出: 2
解釋: 你需要移除兩個(gè) [1,2]?來使剩下的區(qū)間沒有重疊。

示例 3:

輸入: [ [1,2], [2,3]?]
輸出: 0
解釋: 你不需要移除任何區(qū)間，因?yàn)樗鼈円呀?jīng)是無重疊的了。

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[1] < v[1];
????????});

????????int?n = intervals.size();
????????int?right = intervals[0][1];
????????int?ans = 1;
????????for?(int?i = 1; i < n; ++i) {
????????????if?(intervals[i][0] >= right) {
????????????????++ans;
????????????????right = intervals[i][1];
????????????}
????????}
????????return?n - ans;
????}
};