C ++中两个不重叠间隔的最小大小

假设我们有一个间隔列表，其中每个间隔都包含[开始，结束]时间。我们必须找到任何两个非重叠间隔的最小总大小，其中间隔的大小为（结束-开始+ 1）。如果找不到这两个间隔，则返回0。

因此，如果输入类似于[[2,5]，[9,10]，[4,6]]，则输出将为5，因为我们可以选择大小为3的间隔[4,6]和[9]， 10]的尺寸2。

为了解决这个问题，我们将遵循以下步骤-

• ret：= inf

• n：= v的大小

• 根据结束时间对数组v排序

• 定义大小为n的数组dp

• 对于初始化i：= 0，当i <v的大小时，更新（将i增加1），执行-

• dp [i]：= dp [i]和dp [i-1]的最小值

• dp [i]：= val

• ret：=最小值和（temp + val）

• dp [i]：=最小温度和温度

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

• 如果v [mid，1]> = v [i，0]，则-

• 除此以外

• 高：=中-1

• temp：= temp和dp [mid]的最小值

• 低：=中+ 1

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

• 温度：= inf

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

• 当低<=高时，

• 如果temp不等于inf，则-

• 除此以外

• 如果我> 0，那么

• 返回（如果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