【C++】区間を1つ削除した後にカバーされる最大点数を求めるアルゴリズム

はじめに

このチュートリアルでは、区間を1つ削除した後にカバーされる最大の点数を求めるC++プログラムについて解説します。

問題設定は次のとおりです。N個の区間と最大範囲値Qが与えられたとき、1からQまでの範囲において、ある区間を1つ取り除いた際に残りの区間でカバーされる点の数が最大になるような区間を見つけます。

アルゴリズムの考え方

この問題は、次の手順で解くことができます。

1. 被覆数の記録： 各点について、その点をカバーしている区間の本数を配列 Mark に記録します。
2. 総被覆数の集計： Mark を走査し、少なくとも1つの区間に含まれる点の総数 count を求めます。
3. 累積和の構築： 累積和配列 count1 を作り、「その点をカバーする区間がちょうど1本である点」の個数を、任意の区間範囲内で高速に取得できるようにします。
4. 最適な区間の選択： 各区間について「削除後の被覆数 = count − その区間にしか含まれない点の数」を計算し、最大値を与える区間のインデックスを記録します。

ここで重要なのは、ある区間を削除しても失われるのはその区間だけでしかカバーされていない点だけだという点です。複数の区間にまたがってカバーされている点は、削除後も引き続きカバーされたままです。累積和を使えば各区間の「固有の点数」をO(1)で取得できるため、全区間の評価を効率よく行えます。

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++;
    }
    // 「1つの区間にしか含まれない点」の累積和を構築
    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

この例では、インデックス4の区間 {3, 5} を削除しても、1〜7のすべての点が残りの4つの区間で引き続きカバーされるため、最大被覆数7が得られます。一方、例えばインデックス0の区間 {1, 4} を削除すると、点1と点2がどの区間にも含まれなくなるため、被覆数は5に減ってしまいます。

計算量について

このアルゴリズムの時間計算量は O(N × Q) です。各区間の範囲内の点を1つずつマークする処理が支配的となります。NやQが大きいケースでは、差分配列（いもす法）を用いてマーク処理をO(N + Q)に改善できます。また、可変長の範囲を扱う場合は vector<int> を使用すると、より安全で汎用的な実装になります。