C++で重複しない2つの区間のサイズ合計の最小値を求める方法

各要素が開始時刻と終了時刻 [start, end] を持つ区間のリストが与えられたとします。この中から互いに重複しない2つの区間を選び、そのサイズの合計の最小値を求めます。ここで、区間のサイズは (end - start + 1) として定義されます。条件を満たす2つの区間が存在しない場合は 0 を返します。

例えば、入力が [[2,5],[9,10],[4,6]] の場合、出力は 5 になります。これは、サイズ 3 の区間 [4,6] と、サイズ 2 の区間 [9,10] を選ぶことで、合計 5 という最小値が実現できるためです。

解法のアプローチ

この問題は、動的計画法（DP）と二分探索を組み合わせることで効率的に解けます。区間を終了時刻の昇順にソートしておき、各区間ごとに「自分より前の位置にあり、かつ重ならない区間」の最小サイズを二分探索で素早く取得します。これにより、すべてのペアを総当たりする O(n²) の方法よりも高速な O(n log n) で答えを導き出せます。

具体的な手順は以下の通りです。

• ret := inf（答えの初期値）
• n := 配列 v のサイズ
• 終了時刻に基づいて配列 v をソートする
• サイズ n の dp 配列を定義する
• i := 0 から v のサイズ未満まで、i を 1 ずつ増やしながら繰り返し：
  • low := 0、high := i - 1
  • temp := inf
  • val := v[i][1] - v[i][0] + 1（現在の区間のサイズ）
  • low ≤ high の間、次を繰り返す：
    • mid := low + (high - low) / 2
    • v[mid][1] ≥ v[i][0] の場合：high := mid - 1
    • それ以外の場合：temp := min(temp, dp[mid])、low := mid + 1
  • temp ≠ inf の場合：
    • ret := min(ret, temp + val)
    • dp[i] := min(val, temp)
  • それ以外の場合：dp[i] := val
  • i > 0 の場合：dp[i] := min(dp[i], dp[i - 1])
• ret が inf と等しければ 0 を、そうでなければ ret を返す

アルゴリズムのポイント

dp[i] には「インデックス 0 ～ i の範囲で選択可能な区間の最小サイズ」が格納されます。現在の区間 i と重ならない最も右側の候補を二分探索で特定し、そこまでの累積的な最小サイズ（dp の値）を参照することで、無駄な組み合わせの検証を省いています。最後に、求まった最小の合計値 ret を返せば完了です。

理解を深めるために、以下の実装例を見てみましょう。

実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    static bool cmp(vector <int>& a, vector <int>& b){
        return a[1] < b[1];
    }
    int solve(vector<vector<int>>& v) {
        int ret = INT_MAX;
        int n = v.size();
        sort(v.begin(), v.end(), cmp);
        vector <int> dp(n);
        for(int i = 0; i < v.size(); i++){
            int low = 0;
            int high = i - 1;
            int temp = INT_MAX;
            int val = v[i][1] - v[i][0] + 1;
            while(low <= high){
                int mid = low + (high - low) / 2;
                if(v[mid][1] >= v[i][0]){
                    high = mid - 1;
                }else{
                    temp = min(temp, dp[mid]);
                    low = mid + 1;
                }
            }
            if(temp != INT_MAX){
                ret = min(ret, temp + val);
                dp[i] = min(val, temp);
            }else{
                dp[i] = val;
            }
             if(i > 0) dp[i] = min(dp[i], dp[i - 1]);
        }
        return ret == INT_MAX ? 0 : ret;
    }
};
main(){
    Solution ob;
    vector<vector<int>> v = {{2,5},{9,10},{4,6}};
    cout << (ob.solve(v));
}

入力

{{2,5},{9,10},{4,6}}

出力

5

計算量

このアルゴリズムの時間計算量は O(n log n)、必要な追加メモリの空間計算量は O(n) です。ソート後に各区間を一度ずつ処理し、重なり判定を二分探索で行うため、大規模な入力に対しても高速に動作します。