找出最佳间隔以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