C++程式：查詢懸掛所有橫幅所需的最小插銷數

假設我們有一系列 [開始，結束] 格式的區間，表示我們要懸掛的橫幅的開始和結束位置。每個橫幅至少需要一個插銷來懸掛，一個插銷可以懸掛多個橫幅。我們需要找到懸掛所有橫幅所需的最小插銷數。

例如，如果輸入為 intervals = [[2, 5],[5, 6],[8, 10],[10, 13]]，則輸出為 2，因為我們可以將兩個插銷放在位置 5 和 10 來懸掛所有橫幅。

為了解決這個問題，我們將遵循以下步驟：

  • 根據區間的結束值對陣列 v 進行排序。
  • ret := 0
  • last := -inf
  • 對於每個專案 it 在 v 中：
    • 如果 last >= it 的開始位置，則：
      • 忽略以下部分，跳到下一個迭代。
    • （將 ret 增加 1）
    • last := it 的結束位置
  • 返回 ret

示例（C++）

讓我們看看下面的實現以獲得更好的理解：

 線上演示

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   static bool cmp(vector<int>& a, vector<int>& b) {
      return a.back() < b.back();
   }
   int solve(vector<vector<int>>& v) {
      sort(v.begin(), v.end(), cmp);
      int ret = 0;
      int last = -1e8;
      for (auto& it : v) {
         if (last >= it[0]) {
            continue;
         }
         ret++;
         last = it[1];
      }
      return ret;
   }
};
int solve(vector<vector<int>>& intervals) {
   return (new Solution())->solve(intervals);
}
int main(){
   vector<vector<int>> v = {{2, 5},{5, 6},{8, 10},{10, 13}};
   cout << solve(v);
}

輸入

{{2, 5},{5, 6},{8, 10},{10, 13}}

輸出

2

更新於： 2020年12月12日

258 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告