C++-এ একটি ইন্টারভাল সরিয়ে সর্বোচ্চ কভারেজ বের করার প্রোগ্রাম

সমস্যা বিবরণ

Nটি ইন্টারভাল এবং সর্বোচ্চ রেঞ্জ Q দেওয়া থাকলে, একটি ইন্টারভাল সরিয়ে ১ থেকে Q পর্যন্ত সর্বোচ্চ কতগুলো সংখ্যা কভার করা যায় তা বের করুন।

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

1. প্রতিটি ইন্টারভালের জন্য রেঞ্জের সংখ্যাগুলোর কাউন্ট বাড়ান (Mark array)।
2. মোট কভারেজড সংখ্যা গণনা করুন।
3. প্রিফিক্স সম count1[i] = ১ থেকে i পর্যন্ত যেসব সংখ্যা শুধু একবার কভারড।
4. প্রতিটি ইন্টারভাল সরালে কতগুলো "সিঙ্গলি কভারড" সংখ্যা হারাবে তা বের করুন।
5. সর্বোচ্চ total_covered - lost দিনে ইন্টারভালটি বের করুন।

C++ কোড উদাহরণ

#include <bits/stdc++.h>
#define ll long long int
using namespace std;

void solve(int interval[][2], int N, int Q) {
    int Mark[Q] = {0};
    for (int i = 0; i < N; i++) {
        int l = interval[i][0] - 1;
        int r = interval[i][1] - 1;
        for (int j = l; j <= r; j++) Mark[j]++;
    }
    int count = 0;
    for (int i = 0; i < Q; i++) if (Mark[i]) count++;
    
    int count1[Q] = {0};
    if (Mark[0] == 1) count1[0] = 1;
    for (int i = 1; i < Q; i++) {
        if (Mark[i] == 1) count1[i] = count1[i-1] + 1;
        else count1[i] = count1[i-1];
    }
    
    int maxindex, maxcoverage = 0;
    for (int i = 0; i < N; i++) {
        int l = interval[i][0] - 1;
        int r = interval[i][1] - 1;
        int elem1 = (l != 0) ? count1[r] - count1[l-1] : count1[r];
        if (count - elem1 >= maxcoverage) {
            maxcoverage = count - elem1;
            maxindex = i;
        }
    }
    cout << "Maximum Coverage is " << maxcoverage << " after removing interval at index " << maxindex;
}

int main() {
    int interval[][2] = {{1,4}, {4,5}, {5,6}, {6,7}, {3,5}};
    int N = sizeof(interval) / sizeof(interval[0]);
    int Q = 7;
    solve(interval, N, Q);
    return 0;
}

আউটপুট

Maximum Coverage is 7 after removing interval at index 4

জটিলতা

• সময়: O(N × Q + Q)
• স্থান: O(Q)