Minimum Size of Two Non-Overlapping Intervals in C++

สมมติว่าเรามีรายการช่วง (intervals) โดยแต่ละช่วงมี [start, end] เราต้องหาขนาดรวมขั้นต่ำของสองช่วงที่ไม่ทับซ้อนกัน โดยขนาดของช่วงคือ (end - start + 1) หากไม่พบสองช่วงเช่นนั้น ให้คืนค่า 0

เช่น หากอินพุตคือ [[2,5],[9,10],[4,6]] ผลลัพธ์จะเป็น 5 เนื่องจากเราสามารถเลือกช่วง [4,6] ขนาด 3 และ [9,10] ขนาด 2

ขั้นตอนการแก้ปัญหา

• จัดเรียงช่วงตามเวลาสิ้นสุด (end time)
• ใช้ DP: dp[i] = ขนาดน้อยที่สุดของช่วงที่จบไม่เกินช่วง i
• สำหรับแต่ละช่วง i ใช้ Binary Search หาช่วง j ที่จบก่อนช่วง i เริ่ม (v[j][1] < v[i][0])
• อัปเดตคำตอบด้วย dp[j] + size(i)
• คืนค่าผลรวมขนาดน้อยที่สุด หรือ 0 ถ้าไม่พบ

ตัวอย่างโค้ด

#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, n = v.size();
        sort(v.begin(), v.end(), cmp);
        vector<int> dp(n);
        for (int i = 0; i < v.size(); 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));
}

อินพุต

{{2,5},{9,10},{4,6}}

เอาต์พุต

5