এই টিউটোরিয়ালে, আমরা একটি ইন্টারভাল অপসারণের পরে কভার করা সর্বাধিক পয়েন্টগুলি খুঁজে বের করার জন্য একটি প্রোগ্রাম নিয়ে আলোচনা করব
এর জন্য আমাদের N বিরতি এবং সর্বোচ্চ পরিসীমা মান প্রদান করা হবে। আমাদের কাজ হল সেই একটি ব্যবধান খুঁজে বের করা যা সরানো হলে প্রদত্ত পরিসরে 1 থেকে সর্বোচ্চ পরিসরের মান পর্যন্ত আমাদের সর্বাধিক সংখ্যা দেবে
উদাহরণ
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
//finding required interval
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]++;
}
//counting covered numbers
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;
int maxcoverage = 0;
for (int i = 0; i < N; i++) {
int l = interval[i][0] - 1;
int r = interval[i][1] - 1;
int elem1;
if (l != 0)
elem1 = count1[r] - count1[l - 1];
else
elem1 = 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
