C++で削除に最適な区間を見つけるプログラム|メモ化再帰による効率的な解法

問題の概要

互いに重なり合う可能性のある閉区間のリストが与えられます。ここで、「区間を1つ削除し、残りの区間をマージしたうえで、残った区間の数を数える」という操作を考えます。本記事のテーマは、この操作を行ったときに残れる区間数の最大値を求めることです。

たとえば、入力が intervals = [[5, 8], [6, 7], [7, 10], [9, 11]] の場合、出力は 2 になります。それぞれの区間を削除した結果を比較してみましょう。

• [5, 8] を削除した場合 → マージ結果は [6, 11] の1つ
• [6, 7] を削除した場合 → マージ結果は [5, 11] の1つ
• [7, 10] を削除した場合 → マージ結果は [5, 8] と [9, 11] の2つ
• [9, 11] を削除した場合 → マージ結果は [5, 10] の1つ

この中では [7, 10] を削除したときに最も多くの区間が残るため、これが最適な選択であることがわかります。

解法の考え方

すべての削除候補について、残りの区間を毎回ゼロからマージしていては非効率です。そこで、区間をあらかじめソートしておき、メモ化再帰を利用して重複する計算を省くことで、効率的に答えを求めます。具体的な手順は以下の通りです。

1. (終端の値, 区間数) のペアを格納する配列 memo を定義します。
2. 関数 countIntervals(intervals, i, end) を定義します。インデックス i 以降の区間に対して、現在の終端 end を考慮したうえで残せる区間数を返します。
   • i が intervals のサイズと等しい場合は 0 を返します。
   • memo[i].first < end の場合は INT_MIN(−∞相当)を返し、無効な状態であることを示します。
   • memo[i].first == end の場合は計算済みのため、memo[i].second をそのまま返します。
   • end < intervals[i][0](現在の区間が直前の区間と重ならない)の場合は、memo[i] = {min(end, memo[i].first), 1 + countIntervals(intervals, i + 1, intervals[i][1])} で更新し、memo[i].second を返します。
   • それ以外(区間が重なる場合)は、memo[i] = {min(end, memo[i].first), countIntervals(intervals, i + 1, max(intervals[i][1], end))} で更新し、memo[i].second を返します。
3. メイン処理では次のように進めます。
   • memo を intervals のサイズにリサイズし、{INT_MAX, -1} で初期化します。
   • intervals をソートします。
   • count = 0、result = 0、end = -1 で初期化します。
   • i を 0 から intervals のサイズ未満までループさせます。
     • result = max(result, count + countIntervals(intervals, i + 1, end)) として、i 番目の区間を削除したケースの結果で最大値を更新します。
     • end < intervals[i][0] であれば count を1増やします。
     • end = max(end, intervals[i][1]) で終端を更新します。
   • 最後に result を返します。

C++による実装例

以下が実際のコードです。

#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> memo;

int countIntervals(vector<vector<int>>& intervals, int i, int end) {
    if (i == intervals.size()) return 0;
    if (memo[i].first < end)
        return INT_MIN;
    if (memo[i].first == end)
        return memo[i].second;
    if (end < intervals[i][0]) {
        memo[i] = {min(end, memo[i].first), 1 +
            countIntervals(intervals, i + 1, intervals[i][1])};
        return memo[i].second;
    }
    memo[i] = {min(end, memo[i].first),
        countIntervals(intervals, i + 1, max(intervals[i][1],
        end))};
    return memo[i].second;
}

int solve(vector<vector<int>>& intervals) {
    memo.clear();
    memo.resize(intervals.size(), {INT_MAX, -1});
    sort(intervals.begin(), intervals.end());
    int count = 0, result = 0, end = -1;
    vector<int> temp;
    for (int i = 0; i < intervals.size(); i++) {
        result = max(result, count + countIntervals(intervals, i + 1,
            end));
        if (end < intervals[i][0])
            count++;
        end = max(end, intervals[i][1]);
    }
    return result;
}

int main(){
    vector<vector<int>> v = {{5, 8}, {6, 7}, {7, 10}, {9, 11}};
    cout << solve(v);
}

入力

{{5, 8}, {6, 7}, {7, 10}, {9, 11}}

出力

2

まとめ

区間の事前ソートとメモ化再帰を組み合わせることで、各削除候補ごとのマージ結果を効率よく評価できます。今回の例では [7, 10] を削除することで残り区間数が最大化され、答えは 2 となりました。区間のマージやスケジューリングに関連する問題では応用範囲の広いテクニックなので、ぜひ理解しておきましょう。