각 간격에 [시작, 종료] 시간이 포함된 간격 목록이 있다고 가정합니다. 두 개의 겹치지 않는 간격의 최소 총 크기를 찾아야 합니다. 여기서 간격의 크기는 (끝 - 시작 + 1)입니다. 이러한 두 간격을 찾을 수 없으면 0을 반환합니다.
따라서 입력이 [[2,5],[9,10],[4,6]]과 같으면 간격 [4,6]을 선택할 수 있으므로 출력은 5가 됩니다. 크기 3 및 [9,10] 크기 2.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
ret :=inf
-
n :=v의 크기
-
종료 시간을 기준으로 배열 v 정렬
-
크기가 n
인 배열 dp를 정의합니다. -
initialize i :=0의 경우 i
-
낮음 :=0, 높음 :=i - 1
-
임시 :=inf
-
값 :=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] :=발
-
-
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