概要

会議室の予約申請から、時間枠が重ならないように選んだときの利益の合計の最大値を求める問題です。

考察

この問題は、重み付き区間スケジューリング問題の一種です。各申請は時間区間 \([L_i, R_i]\) と利益 \(V_i\) を持ち、重ならない区間の集合を選んで利益の合計を最大化します。

素朴なアプローチでは、区間を終了時間でソートした後、各区間について「この区間を選ぶ場合の最大利益」を計算する動的計画法が考えられます。しかし、単純に実装すると状態数が \(O(N)\)、各状態の計算に \(O(N)\) かかるため、全体で \(O(N^2)\) となり、制約条件の \(N \leq 2 \times 10^5\) では実行時間が間に合いません。

この問題を効率的に解くには、動的計画法の更新を高速化する必要があります。具体的には、区間の終了時間が小さい順に処理し、DP配列を効率的に更新する方法が有効です。

アルゴリズム

1. 申請を終了時間 \(R_i\) の昇順、次に開始時間 \(L_i\) の昇順でソートします
2. DP配列 dp[r] を用意します（dp[r] = 時間枠 \(r\) まで処理したときの最大利益）
3. 時間枠 \(r\) を \(1\) から \(T\) まで順に処理します：
   • dp[r] を dp[r-1] で初期化（この時間枠を使わない選択）
   • 終了時間が \(r\) であるすべての申請について：
     • 申請 \(i\) の開始時間が \(L_i\) の場合、dp[L_i-1] + V_i がこの申請を採用した場合の利益
     • この値で dp[r] を更新可能なら更新
4. 最終的に dp[T] が求める最大利益となります

この手法では、区間の終了時間順に処理することで、DPの更新が効率的に行えます。各申請の処理は定数時間で完了し、全体の計算量は \(O(N \log N + T)\) となります。

計算量

• 時間計算量: \(O(N \log N + T)\)
  • ソートに \(O(N \log N)\)
  • DPの計算に \(O(N + T)\)
• 空間計算量: \(O(N + T)\)
  • イベントリストの格納に \(O(N)\)
  • DP配列の格納に \(O(T)\)

実装のポイント

• 入力データの読み込みとパースを効率的に行う

• 区間を終了時間、開始時間の順でソートする

• DP配列のサイズを \(T+2\) とし、境界条件（\(L_i=0\) の場合）を考慮する

• 同じ終了時間を持つ複数の申請をまとめて処理するために、ソート順とポインタ管理が重要

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        print(0)
        return
    
    n = int(data[0])
    T = int(data[1])
    index = 2
    events = []
    for i in range(n):
        L = int(data[index]); R = int(data[index+1]); V = int(data[index+2])
        index += 3
        events.append((L, R, V))
    
    events.sort(key=lambda x: (x[1], x[0]))
    
    dp = [0] * (T+2)
    j = 0
    for r in range(1, T+1):
        dp[r] = max(dp[r], dp[r-1])
        while j < n and events[j][1] == r:
            L, R, V = events[j]
            if L > 0:
                candidate = dp[L-1] + V
            else:
                candidate = V
            if candidate > dp[r]:
                dp[r] = candidate
            j += 1
            
    print(dp[T])

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。