概要

各申請を「区間 \([L_i, R_i]\) と利益 \(V_i\)」とみなし、時間枠が重ならないように選んだときの利益最大値を求める問題です（重み付き区間スケジューリング）。

考察

重要な気づき

申請同士が重ならない条件は「片方がもう片方の開始より前に完全に終わる」ことです。
申請 \(i\) を採用するなら、その直前に採用できる申請は 終了時刻が \(L_i-1\) 以下のものに限られます（区間が閉区間なので、\(R=L_i\) だと時間枠 \(L_i\) が重なってしまう）。

そこで、 - 「時間枠 \(t\) までで得られる最大利益」を \(dp[t]\) と定義すると、申請 \([L,R]\) を採用して \(R=t\) で終える場合の利益は - \(dp[L-1] + V\) になります。

素朴な方法がダメな理由

例えば - 各申請について「重ならない直前の申請」を探す - あるいは全組み合わせを試す といった方法は、\(N \le 2\times 10^5\) なので \(O(N^2)\) になりやすく TLE します。

この問題では時間枠の上限 \(T \le 2\times 10^5\) も同程度なので、時間 \(t=1..T\) を順にDPし、各時刻で「その時刻に終わる申請」だけを見れば、全体で \(O(N+T)\) にできます。

アルゴリズム

1. 申請を終了時刻ごとにまとめる
   end_at[R] に「終了が \(R\) の申請 \((L,V)\)」を追加する。
2. DP を定義する
   
   • \(dp[t] =\) 時間枠 \(1..t\) の範囲内で、重ならないように申請を選んだときの最大利益
   • 初期値 \(dp[0]=0\)
3. 遷移（\(t=1..T\)）
   まず「何も新しく採用しない」場合：
   • \(dp[t] \ge dp[t-1]\)

次に「\(t\) で終わる申請 \((L,V)\) を採用する」場合： - 利益は \(dp[L-1] + V\)

よって [ dp[t] = \max\Bigl(dp[t-1],\ \max_{(L,V)\in end_at[t]}(dp[L-1]+V)\Bigr) ] 4. 答えは \(dp[T]\)

簡単な例

申請が - \([1,2], V=10\) - \([3,3], V=5\) - \([2,3], V=12\) だとすると、 - \([1,2]\) と \([3,3]\) は重ならない（2 と 3 で連続、共通の整数がない） - \([2,3]\) は他2つと重なりやすい
DPでは、例えば \(t=3\) のとき - 何も増やさない：\(dp[2]\) - \([3,3]\) を採用：\(dp[2]+5\) - \([2,3]\) を採用：\(dp[1]+12\)（\(L-1=1\)） を比べて最大を取ります。

計算量

• 時間計算量: \(O(T + N)\)（各時刻を1回、各申請も1回だけ処理）
• 空間計算量: \(O(T + N)\)（end_at と dp）

実装のポイント

• 区間が 閉区間なので、申請 \([L,R]\) の直前に置けるのは「終了が \(L-1\) 以下」の申請のみ ⇒ 遷移は必ず dp[L-1] + V になる点に注意。

• end_at を T+1 サイズで用意し、end_at[R].append((L,V)) の形でまとめると、DP中に「その時刻に終わる申請」だけを見ればよく高速です。

• \(V_i\) が最大 \(10^9\)、件数も多いので合計は大きくなり得ますが、Python の int なら安全に扱えます。

  ソースコード

import sys

def main():
    input = sys.stdin.buffer.readline
    N, T = map(int, input().split())
    end_at = [[] for _ in range(T + 1)]
    for _ in range(N):
        L, R, V = map(int, input().split())
        end_at[R].append((L, V))

    dp = [0] * (T + 1)
    for t in range(1, T + 1):
        best = dp[t - 1]
        for L, V in end_at[t]:
            cand = dp[L - 1] + V
            if cand > best:
                best = cand
        dp[t] = best

    print(dp[T])

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。