C++での2つの重複しない間隔の最小サイズ

したがって、入力が[[2,5]、[9,10]、[4,6]]の場合、間隔[4,6]を選択できるため、出力は5になります。サイズ3およびサイズ2の[9,10]。

これを解決するには、次の手順に従います-

• ret：=inf

• n：=vのサイズ

• 終了時間に基づいて配列vを並べ替えます

• サイズnの配列dpを定義します

• 初期化i：=0の場合、i

  • 低：=0、高：=i-1

  • temp：=inf

  • val：=v [i、1]-v [i、0] + 1

  • 低<=高、実行

    • 中：=低+（高-低）/ 2

    • v [mid、1]> =v [i、0]の場合、-

      • 高：=中-1

    • それ以外の場合

      • temp：=tempとdp[mid]

        の最小値

      • 低：=中+ 1

  • tempがinfと等しくない場合、-

    • ret：=retの最小値と（temp + val）

    • dp [i]：=valとtempの最小値

  • それ以外の場合

    • dp [i]：=val

  • i> 0の場合、

    • dp [i]：=dp[i]とdp[i-1]の最小値

• return（retがinfと同じ場合は0、それ以外の場合はret）

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   static bool cmp(vector <int>& a, vector <int>& b){
      return a[1] < b[1];
   }
   int solve(vector<vector<int>>& v) {
      int ret = INT_MAX;
      int n = v.size();
      sort(v.begin(), v.end(), cmp);
      vector <int> dp(n);
      for(int i = 0; i < v.size(); i++){
         int low = 0;
         int high = i - 1;
         int temp = INT_MAX;
         int val = v[i][1] - v[i][0] + 1;
         while(low <= high){
            int mid = low + (high - low) / 2;
            if(v[mid][1] >= v[i][0]){
               high = mid - 1;
            }else{
               temp = min(temp, dp[mid]);
               low = mid + 1;
            }
         }
         if(temp != INT_MAX){
            ret = min(ret, temp + val);
            dp[i] = min(val, temp);
         }else{
            dp[i] = val;
         }
            if(i > 0) dp[i] = min(dp[i], dp[i - 1]);
      }
      return ret == INT_MAX ? 0 : ret;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{2,5},{9,10},{4,6}};
   cout << (ob.solve(v));
}

入力

{{2,5},{9,10},{4,6}}

出力

5