Overview

Each request is treated as an “interval \([L_i, R_i]\) with profit \(V_i\)”, and the problem asks for the maximum profit when selecting requests such that their time slots do not overlap (weighted interval scheduling).

Analysis

Key Insight

The condition for two requests not to overlap is that “one completely finishes before the other starts.”
If request \(i\) is selected, the requests that can be selected immediately before it are limited to those with end time at most \(L_i-1\) (since the intervals are closed, if \(R=L_i\), time slot \(L_i\) would overlap).

Therefore, if we define: - \(dp[t]\) = “maximum profit obtainable up to time slot \(t\)”

then the profit from selecting request \([L,R]\) that ends at \(R=t\) is: - \(dp[L-1] + V\)

Why a Naive Approach Doesn’t Work

For example, approaches such as: - Searching for the “nearest non-overlapping preceding request” for each request - Trying all combinations

tend to become \(O(N^2)\) since \(N \le 2\times 10^5\), resulting in TLE.

In this problem, the upper bound of time slots \(T \le 2\times 10^5\) is also of the same order, so by performing DP sequentially for \(t=1..T\) and only examining “requests that end at that time” for each time step, we can achieve an overall complexity of \(O(N+T)\).

Algorithm

1. Group requests by their end time
   Add “request \((L,V)\) with end time \(R\)” to end_at[R].
2. Define the DP
   
   • \(dp[t] =\) maximum profit when selecting non-overlapping requests within the range of time slots \(1..t\)
   • Initial value: \(dp[0]=0\)
3. Transition (\(t=1..T\))
   First, the case where “nothing new is selected”:
   • \(dp[t] \ge dp[t-1]\)

Next, the case where “request \((L,V)\) ending at \(t\) is selected”: - The profit is \(dp[L-1] + V\)

Therefore: [ dp[t] = \max\Bigl(dp[t-1],\ \max_{(L,V)\in end_at[t]}(dp[L-1]+V)\Bigr) ] 4. The answer is \(dp[T]\)

Simple Example

Given requests: - \([1,2], V=10\) - \([3,3], V=5\) - \([2,3], V=12\)

Then: - \([1,2]\) and \([3,3]\) do not overlap (2 and 3 are consecutive, with no common integer) - \([2,3]\) easily overlaps with the other two

In the DP, for example at \(t=3\): - Don’t add anything: \(dp[2]\) - Select \([3,3]\): \(dp[2]+5\) - Select \([2,3]\): \(dp[1]+12\) (\(L-1=1\))

We compare these and take the maximum.

Complexity

• Time complexity: \(O(T + N)\) (each time step is processed once, and each request is processed exactly once)
• Space complexity: \(O(T + N)\) (end_at and dp)

Implementation Notes

• Since the intervals are closed intervals, the only requests that can be placed immediately before request \([L,R]\) are those with “end time at most \(L-1\)” ⇒ Note that the transition is always dp[L-1] + V.

• By preparing end_at with size \(T+1\) and grouping with end_at[R].append((L,V)), you only need to look at “requests ending at that time” during the DP, which is efficient.

• Since \(V_i\) can be up to \(10^9\) and the number of requests can be large, the total can become very large, but Python’s int handles this safely.

  Source Code

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()

---

This editorial was generated by gpt-5.2-high.