2026/05/05

[LeetCode] 435 Non-overlapping Intervals

Greedy

排序區間 : 以終點從小到大

「當前區間」是能向前走最少的區間了

若「下一個區間」跟「當前區間」有重疊

則代表「下一個區間」一定更早出發, 且一定向前走得更遠, 或至少一樣遠

所以「下一個區間」一定比「當前區間」覆蓋更多其他區間

因此把「下一個區間」刪掉肯定穩賺不賠

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
  int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    std::sort(intervals.begin(), intervals.end(),
      [](const vector<int>& v0, const vector<int>& v1) {
        if (v0[1] == v1[1])
          return v0[0] < v0[0];
        return v0[1] < v1[1];
      });

    int remove = 0;
    int last = intervals[0][1];
    for (int i = 1; i < intervals.size(); i++) {
      int start = intervals[i][0];
      int end = intervals[i][1];
      if (start >= last)
        last = end;
      else
        remove++;
    }
    return remove;
  }
};
Labels: