এই টিউটোরিয়ালে, আমরা একটি ইন্টারভাল অপসারণের পরে কভার করা সর্বাধিক পয়েন্টগুলি খুঁজে বের করার জন্য একটি প্রোগ্রাম নিয়ে আলোচনা করব
এর জন্য আমাদের 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