C++で解くビデオステッチング問題：区間[0, T]をカバーする最小クリップ数の求め方

問題概要

長さT秒のスポーツイベントを撮影した複数のビデオクリップがあるとします。これらのクリップは互いに重なり合っており、長さもさまざまです。各クリップclips[i]は1つの区間を表し、時刻clips[i][0]に始まり、時刻clips[i][1]に終わります。

クリップは自由に切断できます。ここで求めたいのは、イベント全体の区間[0, T]を完全にカバーできるようにクリップを切り貼りするために必要な最小のクリップ数です。カバーが不可能な場合は-1を返します。

例えば、入力が[[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]]、T = 10の場合、答えは3になります。クリップ[0,2]・[8,10]・[1,9]の計3つを選び、[1,9]を[1,2] + [2,8] + [8,9]というセグメントに切断すれば、[0,2] + [2,8] + [8,10]となり、イベント全体[0, 10]をちょうど覆うことができます。

解法のアプローチ（貪欲法）

この問題は貪欲法（グリーディ法）で効率よく解けます。各開始時刻について「その時刻から最も遠くまで届く終了時刻」をあらかじめ記録しておき、現在到達できる範囲を少しずつ前進させていくイメージです。具体的な手順は以下の通りです。

• サイズT + 1の配列vを作成し、すべて-1で初期化する
• n := clipsの要素数とする
• iを0からn - 1まで繰り返す
  • clips[i][0] > T の場合は次の反復へスキップする
  • v[clips[i][0]] := max(v[clips[i][0]], min(clips[i][1], T)) を代入する
• curr := v[0] とする
• v[0]が-1なら-1を返す（時刻0から始まるクリップが存在しないため）
• i := 1、ret := 1、next := 0 と初期化する
• curr < T かつ i <= n の間、以下を繰り返す
  • i <= curr の間、next := max(next, v[i]) としてiを1ずつ増やす
  • next == curr または next == -1 の場合は-1を返す（これ以上先へ進めないため）
  • curr := next とし、retを1増やす
• curr >= T ならretを返し、そうでなければ-1を返す

C++実装例

それでは、実際のコードを見て理解を深めましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int videoStitching(vector<vector<int>>& clips, int T) {
        vector<int> v(T + 1, -1);
        int n = clips.size();
        for(int i = 0; i < n; i++){
            if(clips[i][0] > T)continue;
            v[clips[i][0]] = max(v[clips[i][0]], min(clips[i][1], T));
        }
        int curr = v[0];
        if(v[0] == -1)return -1;
        int i = 1;
        int ret = 1;
        int next = 0;
        while(curr < T && i <= n){
            while(i <= curr){
                next = max(next, v[i]);
                i++;
            }
            if(next == curr || next == -1) return -1;
            curr = next;
            ret++;
        }
        return curr >= T ? ret : -1;
    }
};
main(){
    vector<vector<int>> v1 = {{0,2},{4,6},{8,10},{1,9},{1,5},{5,9}};
    Solution ob;
    cout << (ob.videoStitching(v1, 10));
}

入力

[[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]]
10

出力

3

処理のポイントと計算量

配列vには「各時刻からジャンプできる最大の時刻」が格納されます。この構造は「ジャンプゲーム」と同様であり、現在位置currから到達可能な範囲内で最も遠い到達点nextを更新しながら、クリップを1枚追加するごとにcurrをnextへ進めていきます。途中で到達点が更新できなくなった場合（next == curr または next == -1）、区間[0, T]のカバーは不可能なので-1を返します。

時間計算量はO(n + T)、空間計算量はO(T)であり、クリップ数やイベント長に対して非常に効率的に動作します。