資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++中兩個不相交區間的最小大小
假設我們有一系列區間，每個區間包含[開始時間，結束時間]。我們必須找到任意兩個不相交區間的最小總大小，其中區間的尺寸為(結束時間 - 開始時間 + 1)。如果找不到這樣的兩個區間，則返回0。
因此，如果輸入類似於[[2,5],[9,10],[4,6]]，則輸出將為5，因為我們可以選擇大小為3的區間[4,6]和大小為2的區間[9,10]。
為了解決這個問題，我們將遵循以下步驟：
ret := ∞
n := v的大小
根據結束時間對陣列v進行排序
定義一個大小為n的陣列dp
for 初始化 i := 0，當 i < v的大小，更新 (i 增加 1)，執行：
low := 0, high := i - 1
temp := ∞
val := v[i, 1] - v[i, 0] + 1
while low <= high，執行：
mid := low + (high - low) / 2
if v[mid, 1] >= v[i, 0]，則：
high := mid - 1
否則
temp := temp 和 dp[mid] 的最小值
low := mid + 1
if temp 不等於 ∞，則：
ret := ret 和 (temp + val) 的最小值
dp[i] := val 和 temp 的最小值
否則
dp[i] := val
if i > 0，則
dp[i] := dp[i] 和 dp[i - 1] 的最小值
return (如果 ret 等於 ∞，則返回 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
更新於：2020年9月2日
213 次瀏覽
廣告