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