いわゆる、「重み付き区間スケジューリング問題」のもっとも基本的な問題です。これは、以下のようなアルゴリズムで可能です。

まず、申請を終了時刻 \(R_i\) の昇順に並べ、その順に index をふり直します。

• \(dp[i] =\)「\(1 \dots i\) だけを考えたときの利益の最大値」

として貰う DP を考えると、申請 \(i\) について

• 申請 \(i\) を承認しない場合

  \(dp[i-1]\) が最大値となります。

• 申請 \(i\) を承認する場合

  これまでに承認した申請すべてが \(R_j<L_i\) を満たしてなければいけません。\(R\) の昇順に並べましたから、これを満たすような申請の個数を \(j\) として、 \(dp[j] + V_i\) が最大値となります。

よって、 \(dp[i] = \max\left(dp[i-1],\,dp[j]+V_i\right)\) と更新できます。

\(j\) は二分探索で求められることを考えると、ソートと二分探索を合わせて計算量は \(O(N\log N)\) です。

実装例

from bisect import bisect_left
n, t = map(int, input().split())
a = []
for _ in range(n):
    l, r, v = map(int, input().split())
    a.append((r, l, v))

a.sort()
rs = [r for r, l, v in a]

dp = [0] * (n + 1)

for i in range(n):
    r, l, v = a[i]
    j = bisect_left(rs, l)
    dp[i+1] = max(dp[i], dp[j] + v)

print(dp[n])