अंतरालों की सूची दी गई है [start, end]। दो असंयोगी (non-overlapping) अंतराल चुनें जिनके आकार (end-start+1) का योग न्यूनतम हो।
अंत समय के अनुसार सॉर्ट करें। DP + बाइनरी सर्च: प्रत्येक अंतराल के लिए, उससे पहले खत्म होने वाले न्यूनतम आकार वाले अंतराल को बाइनरी सर्च द्वारा खोजें।
उदाहरण: {{2,5},{9,10},{4,6}} → [4,6] आकार 3 और [9,10] आकार 2 → कुल 5।
C++ कार्यान्वयन
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
static bool cmp(vector& a, vector& b) { return a[1] < b[1]; }
int solve(vector>& v) {
int ret = INT_MAX;
int n = v.size();
sort(v.begin(), v.end(), cmp);
vector dp(n);
for (int i = 0; i < v.size(); i++) {
int low = 0, 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;
}
};
int main() {
Solution ob;
vector> v = {{2,5},{9,10},{4,6}};
cout << ob.solve(v);
return 0;
}
इनपुट
{{2,5},{9,10},{4,6}}
आउटपुट
5