C++で削除するのに最適な間隔を見つけるためのプログラム

重複する可能性のある間隔のリスト（両端を含む）があるとします。ここで、1つの間隔を削除し、残りの間隔をマージして、残りの間隔の数をカウントする操作があると考えてください。削除後に可能な残りの間隔の最大数を見つける必要があります。

したがって、入力が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（）を定義します。これには、1つの2D配列間隔i、endが必要です。

  • iが音程のサイズと同じである場合、-

    • 0を返す

  • memo [i] .first_element

    • −無限大を返します。

  • memo [i] .first_elementがendと同じ場合、-

    • memo [i]

      の2番目の要素を返す

  • end

    • memo [i]：=memo [i]の最後と最初の最小値、1 + countIntervals（intervals、i + 1、intervals [i、1]）

    • memo [i]

      の2番目の要素を返す

  • memo [i]：=memo [i]の終了と最初の要素の最小値とcountIntervals（intervals、i + 1、intervals [I、1]とendの最大値）

  • memo [i]

    の2番目の値を返します

• メインの方法から、次のようにします-

  • 配列メモのサイズを間隔のサイズに変更します

  • 配列間隔を並べ替える

  • カウント：=0、結果：=0、終了：=− 1

  • アレイの温度を定義する

  • for i：=0からi<間隔のサイズ、更新（iを1増やします）、実行-

    • 結果：=結果とカウントの最大値+ countIntervals（intervals、i + 1、end）

    • end

      • （カウントを1つ増やします）

    • end：=終了と間隔の最大値[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