Kích thước nhỏ nhất của 2 khoảng không giao nhau trong C++

Cho danh sách khoảng [start, end]. Tìm tổng kích thước nhỏ nhất của 2 khoảng không giao nhau (kích thước = end-start+1). Không tìm được → 0.

Thuật toán (Sắp xếp + Binary Search + DP)

• Sắp xếp khoảng theo end tăng dần.
• dp[i]: kích thước nhỏ nhất của 1 khoảng trong tiền tố [0..i].
• Với khoảng i: tìm khoảng j < i có end < start_i (binary search). Cập nhật ans = min(ans, size_i + dp[j]).
• Cập nhật dp[i] = min(size_i, dp[j], dp[i-1]).

Ví dụ triển khai (C++)

#include <bits/stdc++.h>
using namespace std;

class Solution {
    static bool cmp(vector<int>& a, vector<int>& b) { return a[1] < b[1]; }
public:
    int solve(vector<vector<int>>& v) {
        int ret = INT_MAX, n = v.size();
        sort(v.begin(), v.end(), cmp);
        vector<int> dp(n);
        for (int i = 0; i < n; i++) {
            int low = 0, high = i-1, 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<vector<int>> v = {{2,5},{9,10},{4,6}};
    cout << ob.solve(v);
    return 0;
}

Đầu ra

5