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 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告