資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++程式：找出最佳刪除區間
假設我們有一系列可能重疊的區間（包含端點）。現在考慮一個操作，我們刪除一個區間，然後合併剩餘的區間，最後計算剩餘區間的數量。我們需要找到刪除一個區間後可能剩餘的最大區間數量。
例如，如果輸入區間為 intervals = [ [5, 8], [6, 7], [7, 10], [9, 11]]，則輸出為 2。這是因為：
如果我們刪除區間 [5, 8]，則合併後的區間為 [6, 11]。
如果我們刪除區間 [6, 7]，則合併後的區間為 [5, 11]。
如果我們刪除區間 [7, 10]，則合併後的區間為 [5, 8], [9, 11]。
如果我們刪除區間 [9, 11]，則合併後的區間為 [5, 10]。
因此，刪除 [7, 10] 是最佳方案。
為了解決這個問題，我們將遵循以下步驟：
定義一個儲存數字對的陣列 memo。
定義一個函式 countIntervals()，它將接收一個二維陣列 intervals、索引 i 和結束值 end。
如果 i 等於 intervals 的大小，則：
返回 0
如果 memo[i] 的第一個元素小於 end，則：
返回負無窮大。
如果 memo[i] 的第一個元素等於 end，則：
返回 memo[i] 的第二個元素
如果 end < intervals[i, 0]，則：
memo[i] := min(end, memo[i].first) , 1 + countIntervals(intervals, i + 1, intervals[i, 1])
返回 memo[i] 的第二個元素
memo[i] := min(end, memo[i].first) , countIntervals(intervals, i + 1, max(intervals[i, 1], end))
返回 memo[i] 的第二個值
在主方法中執行以下操作：
將陣列 memo 的大小調整為 intervals 的大小
對陣列 intervals 進行排序
count := 0, result := 0, end := -1
定義一個數組 temp
對於 i := 0 到 i < intervals 的大小，更新 (i 增加 1)，執行：
result := max(result, count + countIntervals(intervals, i + 1, end))
如果 end < intervals[i, 0]，則：
(count 增加 1)
end := max(end, intervals[i, 1])
返回 result
讓我們看看下面的實現，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> memo;
int countIntervals(vector<vector<int>>& intervals, int i, int end) {
if (i == intervals.size()) return 0;
if (memo[i].first < end)
return INT_MIN;
if (memo[i].first == end)
return memo[i].second;
if (end < intervals[i][0]) {
memo[i] = {min(end, memo[i].first), 1 +
countIntervals(intervals, i + 1, intervals[i][1])};
return memo[i].second;
}
memo[i] = {min(end, memo[i].first),
countIntervals(intervals, i + 1, max(intervals[i][1],
end))};
return memo[i].second;
}
int solve(vector<vector<int>>& intervals) {
memo.clear();
memo.resize(intervals.size(), {INT_MAX, −1});
sort(intervals.begin(), intervals.end());
int count = 0, result = 0, end = −1;
vector<int> temp;
for (int i = 0; i < intervals.size(); i++) {
result = max(result, count + countIntervals(intervals, i + 1,
end));
if (end < intervals[i][0])
count++;
end = max(end, intervals[i][1]);
}
return result;
}
int main(){
vector<vector<int>> v = {{5, 8}, {6, 7}, {7, 10}, {9, 11}};
cout<<solve(v);
}輸入
{{5, 8}, {6, 7}, {7, 10}, {9, 11}}輸出
2
瀏覽量：145
