設問とユースケース
各ジョブは (start, end, reward) です。総報酬が最大となる両立可能なジョブを選択してください。終了時刻が次の開始時刻と等しい場合は許容されます。(1,3,50), (3,5,40), (2,6,100) の場合、最初の2つのジョブを選択することで報酬 90 が得られます。これは実装言語を問わず、区間の順序付け、直前要素の検索、動的計画法をテストする coding の問題です。
公開されているアルゴリズム教材では、重み付き区間/ジョブスケジューリングを動的計画法および区間パターンの演習として扱っており、公開されている面接体験談にも区間スケジューリングの変種が記録されています。検証不可能な面接の出題頻度を主張することなく、検証可能な要件を述べてください。
面接官が評価するポイント
- 終了時刻でソートし、最後に選択したジョブが順序付けられた決定を形成するようにしているか。
- ジョブ
iの開始時刻以前に終了する最後のジョブであるp(i)を定義しているか。 - 単に最大の個別報酬を貪欲に選ぶのではなく、現在のジョブをスキップする場合と採用する場合を比較しているか。
- 二分探索によって直前要素の検索を
O(log n)に削減できているか、また選択したジョブを復元できるか。 end == start、終了時刻の一致、空の入力、報酬ゼロのケースを適切に処理しているか。
回答前の明確化事項
- 終了時刻と開始時刻が等しい場合は両立可能ですか？ この回答では yes（
end <= start）と仮定します。 - 報酬が負になることはありますか？ その場合、ジョブを1つも選ばない（ベースライン
0）ことを明示的に許可します。 - 最大報酬のみが求められていますか？ この記事ではジョブの集合も復元します。不要であれば親データの保持は省略してください。
- 時刻は整数ですか？ ソートには比較可能性のみが必要であり、二分探索に連続する整数は不要です。
- 同じジョブを2回選択できますか？ 入力の各ジョブは最大1回のみ選択可能と仮定します。
start > endは発生しますか？ 漸化式の前に拒絶または正規化してください。無効なデータをそのままにしないでください。- 同一の区間はどのように順序付けるべきですか？ 安定なタイブレークを使用してください。最適な報酬であればどれでも許容されます。
30秒回答フレームワーク
「ジョブを end でソートし、dp[i] を最初の i 個のジョブから得られる最良の報酬と定義します。ジョブ i について、終了時刻が最大でも start[i] である最後のジョブを二分探索し、その両立可能なプレフィックスのサイズを p とします。漸化式は dp[i] = max(dp[i-1], reward[i] + dp[p]) となり、ジョブをスキップするか、両立可能なプレフィックスとともに採用します。選択マーカーを保持し、バックトラックしてジョブを復元します。ソートと各二分探索により時間計算量は O(n log n) となり、配列は O(n) の空間を使用します。」
ステップバイステップの詳細な回答
ステップ 1: 貪欲法では不十分な理由を説明する。
最も早く終了するジョブを選ぶ貪欲法は、すべてのジョブの価値が等しい場合には正しく機能します。報酬が異なる場合、短くて価値の低いジョブがより良い組み合わせをブロックする可能性があるため、局所的な終了時刻や局所的な報酬だけでは不十分です。
ステップ 2: 順序付けられた状態を定義する。
ソート後、dp[i] をジョブ 0..i-1 に対する最適値とし、dp[0] = 0 とします。ジョブ i-1 をスキップすると直ちに dp[i-1] が得られます。
ステップ 3: 直前のジョブを計算する。
ジョブ i-1 について、end[j] <= start[i-1] を満たす最大の j < i-1 を見つけます。ソートされた終了時刻に対して二分探索を行い、両立可能なプレフィックスのサイズ p を返します。このジョブを採用すると reward[i-1] + dp[p] が得られます。
ステップ 4: 漸化式と経路復元を記述する。
dp[0] = 0
for i = 1..n:
skip = dp[i - 1]
take = reward[i - 1] + dp[p(i - 1)]
dp[i] = max(skip, take)
chose[i] = take > skipi = n からバックトラックします。chose[i] が真であればジョブ i-1 を記録して p(i-1) にジャンプし、そうでなければ i をデクリメントします。収集したリストを反転します。2つの報酬が等しい場合のタイブレークを固定します。
ステップ 5: 正当性を証明する。
最初の i 個のジョブに対する任意の最適解は、ジョブ i-1 を除外して最大 dp[i-1] を得るか、これを含めるかのいずれかです。後者の場合、他のすべてのジョブは最初の p(i-1) 個の両立可能なジョブに含まれるため、最大 reward[i-1] + dp[p(i-1)] を得ます。漸化式はこれらの網羅的なケースのうち大きい方を選択します。基底ケース dp[0] = 0 とともに、数学的帰納法によりすべての状態が最適であることが証明されます。
ステップ 6: 実装の境界条件を保護する。
隣接するジョブが両立可能であり続けるよう、直前要素の検索では <= を使用する必要があります。負の報酬および空集合に対応するため、0から開始します。復元は末尾から実行されるため、バックトラックの結果を反転します。
ステップ 7: 計算量を分析する。
ソートには O(n log n) かかり、ジョブごとの二分探索も合計で O(n log n) かかります。動的計画法、直前要素、選択用の配列は O(n) の空間を使用します。出力サイズをカウントする場合は別途記述してください。
ステップ 8: 代替案を特定する。
終了時刻が小さな有界整数である場合、時刻をインデックスとするスキャンによって比較ソートを回避できます。報酬が等しい場合は、終了時刻順の貪欲法で十分です。最大 k 個のジョブという制限や複数のリソースがある場合は状態の次元が増加し、新しい漸化式が必要になります。
質の高い模範解答
「終了時刻でソートし、最初の i 個のジョブにおける最大報酬として dp[i] を定義します。各ジョブについて、end <= start を満たす最後の直前ジョブを二分探索します。スキップすると dp[i-1]、採用すると reward[i] + dp[p(i)] が得られるため、大きい方を保持してバックトラック用に選択を記録します。証明では、すべての最適解を現在のジョブを含むかどうかで分割します。含む場合、残りのジョブは両立可能なプレフィックスから取得する必要があります。ソートと二分探索により時間計算量は O(n log n)、補助空間は O(n) となります。隣接するジョブ、終了時刻の一致、負の報酬、完全な重複、空の入力についてテストします。」
よくあるミス
- 最大報酬による貪欲法 → 1つのジョブがより合計値の高い組み合わせをブロックする可能性がある → DP で採用とスキップを比較する。
- 終了/開始の一致を重複として扱う → 正当な隣接ジョブが除外される →
end <= startを使用する。 - 開始時刻のみでソートする →
dp[i-1]が安定したプレフィックスを表さなくなる → 終了時刻でソートする。 - 直前要素の線形スキャン → 合計時間が
O(n²)になる → 終了時刻を二分探索する。 - 最初の報酬で初期化する → すべて負の入力のときに空集合を選択できなくなる →
dp[0] = 0を設定する。 - バックトラックの反転忘れ → 選択されたジョブが逆順で返される → 収集後に反転する。
- 報酬が等しい場合のタイブレークが未指定 → 実行ごとに出力が変わる → タイブレークを固定する。
- 1次元でリソース制限を処理できると主張する → 追加の制約が表現されない → 次元を追加するかモデルを再構築する。
フォローアップの質問と回答
フォローアップ 1: なぜ等号境界のルールが安全なのですか？
あるジョブの終了時刻が別のジョブの開始時刻とちょうど一致する場合、提示された規約のもとでは重複しません。したがって、直前要素の判定には等号を含める必要があり、< に変更すると別の問題を解くことになります。
フォローアップ 2: これは常に O(n) にできますか？
小さな有界整数の時刻であれば、直接の時間スキャンによって線形時間にできます。一般的な比較モデルではソート自体に O(n log n) かかるため、無条件で線形時間を約束しないでください。
フォローアップ 3: ジョブをどのように復元しますか？
選択ビットまたは親ポインタを保持します。i = n から開始し、現在のジョブを採用してその直前要素にジャンプするか、スキップ時にデクリメントします。収集したジョブを反転します。
フォローアップ 4: 最大 k 個のジョブしか選択できない場合はどうなりますか？
最初の i 個のジョブのうち c 個のジョブを使用した最良の報酬として、dp[i][c] のような個数の次元を追加します。時間と空間はそれに応じて増加します。
フォローアップ 5: 報酬が隣接するジョブに依存する場合はどうなりますか？
報酬が独立しているという前提が成り立たなくなります。隣接関係を状態に含めるか、遷移コストとしてモデル化してください。その変更なしには元の漸化式は正当化されません。
フォローアップ 6: すべてのジョブの終了時刻が同じ場合はどうなりますか？
安定ソートで十分です。それらの直前要素は通常同一であり、漸化式は引き続き各候補を比較します。同一の区間については、最良の報酬のみが重要となります。
フォローアップ 7: 貪欲法が正しいのはどのような場合ですか？
すべての報酬が等しく、ジョブ数を最大化することが目的である場合、終了時刻順の貪欲法には交換補題（exchange argument）が成り立ちます。報酬が異なる場合は、重み付き動的計画法を使用してください。