資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
廣告