C++ 中两个不重叠区间的最小长度
c++server side programmingprogramming
假设我们有一个区间列表，每个区间包含 [起始时间, 结束时间]。我们需要找出任意两个不重叠区间的最小长度总和，其中区间的长度为 (结束时间 - 起始时间 + 1)。如果找不到这两个区间，则返回 0。
因此，如果输入为 [[2,5],[9,10],[4,6]]，则输出为 5，因为我们可以选择大小为 3 的区间 [4,6] 和大小为 2 的区间 [9,10]。
为了解决这个问题，我们将遵循以下步骤 −
ret := inf
n := v 的大小
根据结束时间对数组 v 进行排序
定义一个大小为 n 的数组 dp
初始化 i := 0，当 i < v 的大小，更新(将 i 加 1)，执行 −
low := 0, high := i - 1
temp := inf
val := v[i, 1] - v[i, 0] + 1
当 low <= high 时，执行
mid := low + (high - low) / 2
如果 v[mid, 1] >= v[i, 0]，则执行 −
high := mid - 1
否则
temp := temp 与 dp[mid] 的最小值
low := mid + 1
如果 temp 不等于 inf，则 −
ret := ret 与 (temp + val) 的最小值
dp[i] := val 与 temp 的最小值
否则
dp[i] := val
如果 i > 0，则
dp[i] := dp[i] 与 dp[i - 1] 中的最小值
返回(如果 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
