সি++-এ ইন্টারভ্যাল মুছে ফেলে বাকি মেড করায় সর্বোচ্চ ইন্টারভ্যাল পাওয়ার প্রোগ্রাম

সমস্যা বিবরণ

ওভারল্যাপিং ইন্টারভ্যালের একটি লিস্ট দেওয়া আছে। একটি ইন্টারভ্যাল ডিলিট করে বাকিগুলো মার্জ করলে সর্বোচ্চ কতগুলো ইন্টারভ্যাল বাকি থাকে তা বের করতে হবে।

উদাহরণ: intervals = [[5,8], [6,7], [7,10], [9,11]]

আউটপুট: 2

ব্যাখ্যা:

• [5,8] ডিলিট → [6,11] (১টি)
• [6,7] ডিলিট → [5,11] (১টি)
• [7,10] ডিলিট → [5,8], [9,11] (২টি) ✓
• [9,11] ডিলিট → [5,10] (১টি)

সমাধানের পদ্ধতি

ডাইনামিক প্রোগ্রামিং + মেমোইজেশন:

1. ইন্টারভ্যালগুলো সর্ট করুন।
2. countIntervals(i, end) = ইনডেক্স i থেকে শেষ পর্যন্ত end পর্যন্ত মেড করার পরে ইন্টারভ্যাল সংখ্যা।
3. প্রতিটি ইন্টারভ্যাল কে "ডিলিট করা" ধরে বাকিগুলোর মেড ইন্টারভ্যাল কাউন্ট করুন।
4. সর্বোচ্চ কাউন্ট রিটার্ন করুন।

উদাহরণ কোড

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

vector<pair<int,int>> memo;

int countIntervals(vector<vector<int>>& intervals, int i, int end) {
    if (i == intervals.size()) return 0;
    if (memo[i].first < end) return INT_MIN;
    if (memo[i].first == end) return memo[i].second;
    if (end < intervals[i][0]) {
        memo[i] = {min(end, memo[i].first), 1 + countIntervals(intervals, i+1, intervals[i][1])};
        return memo[i].second;
    }
    memo[i] = {min(end, memo[i].first), countIntervals(intervals, i+1, max(intervals[i][1], end))};
    return memo[i].second;
}

int solve(vector<vector<int>>& intervals) {
    memo.clear();
    memo.resize(intervals.size(), {INT_MAX, -1});
    sort(intervals.begin(), intervals.end());
    int count = 0, result = 0, end = -1;
    for (int i = 0; i < intervals.size(); i++) {
        result = max(result, count + countIntervals(intervals, i+1, end));
        if (end < intervals[i][0]) count++;
        end = max(end, intervals[i][1]);
    }
    return result;
}

int main() {
    vector<vector<int>> v = {{5,8},{6,7},{7,10},{9,11}};
    cout << solve(v);
    return 0;
}

ইনপুট ও আউটপুট

ইনপুট: {{5,8},{6,7},{7,10},{9,11}}

আউটপুট: 2