C++ में एक अंतराल हटाने के बाद अधिकतम कवर किए गए बिंदु

N अंतराल और अधिकतम रेंज मान Q दिया गया है। एक अंतराल हटाएं ताकि 1 से Q तक कवर किए गए पूर्णांकों की संख्या अधिकतम हो।

प्रत्येक बिंदु की कवरेज गिनें। फिर प्रत्येक अंतराल के लिए, उसके द्वारा विशिष्ट रूप से कवर किए गए बिंदु घटाकर शेष कवरेज देखें।

उदाहरण: अंतराल {{1,4},{4,5},{5,6},{6,7},{3,5}}, Q=7 → अंतराल इंडेक्स 4 हटाने पर अधिकतम कवरेज 7।

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, 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