数据结构
网络
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
