Maximum points covered after removing an Interval in C++

ในบทช่วยสอนนี้ เราจะพูดถึงโปรแกรมหาจุดที่ครอบคลุมสูงสุดหลังจากลบช่วง (Interval) หนึ่งช่วง

เราจะได้รับ N ช่วงและค่าช่วงสูงสุด งานคือหาช่วงนั้นที่เมื่อลบออกจะให้จำนวนสูงสุดในช่วงที่กำหนดจาก 1 ถึงค่าสูงสุด

ตัวอย่างโค้ด

#include <bits/stdc++.h>
#define ll long long
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