C++-এ দুটি নন-ওভারল্যাপিং ইন্টারভালের ন্যূনতম মোট আকার বের করার প্রোগ্রাম

সমস্যা বিবরণ

ইন্টারভালের একটি লিস্ট দেওয়া থাকলে (প্রতিটি [start, end]), দুটি নন-ওভারল্যাপিং ইন্টারভাল বের করুন যাতে তাদের মোট আকার (end - start + 1) ন্যূনতম হয়। না পাওয়া গেলে 0 রিটার্ন করুন।

সমাধানের পদ্ধতি (Sort + DP + Binary Search)

1. ইন্টারভালগুলো এন্ড টাইম অনুযায়ী সর্ট করুন।
2. dp[i] = প্রথম i+1 ইন্টারভাল থেকে নন-ওভারল্যাপিং সাবসেটের ন্যূনতম আকার।
3. প্রতি ইন্টারভাল i-এর জন্য:
   • বাইনারি সার্চ দিয়ে এমন সর্বোচ্চ j খুঁজুন যাতে v[j][1] < v[i][0] (নন-ওভারল্যাপ)۔
   • temp = min(dp[0..j])।
   • val = v[i][1] - v[i][0] + 1।
   • dp[i] = min(val, temp)।
   • ret = min(ret, temp + val)।
4. dp[i] = min(dp[i], dp[i-1]) (প্রিফিক্স মিন)۔

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;
}

আউটপুট

5

ব্যাখ্যা

সর্টেড: [2,5], [4,6], [9,10]

[4,6] আকার ৩, [9,10] আকার ২ → মোট ৫ (নন-ওভারল্যাপ)۔

জটিলতা

• সময়: O(n log n)
• স্থান: O(n)