Điểm bao phủ tối đa sau khi xóa một khoảng trong C++

Cho N khoảng [l,r] và phạm vi Q. Xóa 1 khoảng để số lượng số nguyên trong [1,Q] được bao phủ bởi các khoảng còn lại là lớn nhất.

Thuật toán

• Mảng Mark[x]: số khoảng bao phủ x.
• count: tổng số x có Mark[x] > 0.
• Mảng count1[x]: số y ≤ x có Mark[y] == 1 (chỉ bị 1 khoảng bao phủ).
• Với mỗi khoảng i: số điểm chỉ bị i bao phủ = count1[r] - count1[l-1].
• Bao phủ sau khi xóa i = count - chỉ_bị_i_bao_phủ. Chọn max.

Ví dụ triển khai (C++)

#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++)
        for (int j = interval[i][0]-1; j <= interval[i][1]-1; 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++)
        count1[i] = count1[i-1] + (Mark[i]==1);
    int maxcoverage = 0, maxindex = 0;
    for (int i = 0; i < N; i++) {
        int l = interval[i][0]-1, r = interval[i][1]-1;
        int only_i = (l? count1[r]-count1[l-1] : count1[r]);
        if (count - only_i >= maxcoverage) {
            maxcoverage = count - only_i;
            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 = 5, Q = 7;
    solve(interval, N, Q);
    return 0;
}

Đầu ra

Maximum Coverage is 7 after removing interval at index 4