找出最佳间隔以C ++删除的程序
假设我们有一个可能重叠的区间列表（含）。现在考虑存在一种操作，其中我们删除一个间隔，然后合并剩余的间隔，然后计算剩余的间隔数。我们必须找到移除后可能的最大剩余间隔数。
因此，如果输入就像interval = [[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]是完美的。
为了解决这个问题，我们将遵循以下步骤-
定义数字对的数组备忘，
定义一个函数countIntervals()，这将花费一个2D数组间隔，即结束。
memo [i]：= memo [i]的结尾和开头的最小值，1 + countIntervals（intervals，i + 1，interval [i，1]）
返回备忘录的第二个元素[i]
返回备忘录的第二个元素[i]
返回-infinity。
返回0
如果我与间隔的大小相同，则-
如果memo [i] .first_element <end，则-
如果memo [i] .first_element与end相同，则-
如果end <interval [i，0]，则-
memo [i]：= memo [i]的结尾和第一个元素的最小值和countIntervals（间隔，i + 1，最大的间隔为[I，1]和结束）
返回备忘录的第二个值[i]
从主要方法中执行以下操作-
结果：=结果和计数的最大值+ countIntervals（间隔，i + 1，结束）
如果end <interval [i，0]，则-
end：= end和interval的最大值[i，1]
（增加1）
将数组备忘调整为间隔大小
对数组间隔进行排序
计数：= 0，结果：= 0，结束：= − 1
定义阵列温度
对于i：= 0至i <间隔大小，更新（将i增加1），-
返回结果
让我们看下面的实现以更好地理解-
示例
#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
以上是 找出最佳间隔以C ++删除的程序 的全部内容， 来源链接： utcz.com/z/315922.html
