数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律学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 的结束位置
- 如果 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 次浏览
广告