Overview

This problem involves selecting non-overlapping meetings within time slots to maximize the total profit. It is an application of interval scheduling, solved efficiently using dynamic programming and a segment tree.

Analysis

First, as a naive approach, we consider sorting the requests in some order and greedily selecting them from the beginning. However, simply sorting by start time or end time and greedily picking them does not yield the optimal solution. This is because each interval has a value (profit \(V_i\)), so shorter intervals with higher value should still be selected.

Therefore, we consider the “interval scheduling with values” approach: sort by end time in ascending order and then apply dynamic programming (DP). This becomes effective by defining the following DP table:

• \(\mathrm{dp}[t] :=\) the maximum profit obtainable up to time \(t\)

However, with a naive array-based DP, when processing a request \((L_i, R_i, V_i)\), computing “\(\max_{k=0}^{L_i - 1} \mathrm{dp}[k]\)” each time results in an overall complexity of \(O(N^2)\), which is too slow for the constraint \(N \leq 2 \times 10^5\).

To perform these maximum queries and updates efficiently, we use a data structure such as a segment tree. Specifically, by using a segment tree that supports range maximum queries and point updates, each operation can be performed in \(O(\log T)\), making the overall solution sufficiently fast.

Algorithm

1. Sort each request \((L_i, R_i, V_i)\) in ascending order of end time \(R_i\).
2. Prepare a segment tree, managing \(\mathrm{seg}[t] :=\) the maximum profit when using time up to \(t\).
3. For each request:
   • Retrieve the maximum profit before the start time from the segment tree: \(\max_{k=0}^{L_i - 1} \mathrm{seg}[k]\)
   • Calculate the new profit obtainable by using this request: \(\text{new\_val} = \max_{k=0}^{L_i - 1} \mathrm{seg}[k] + V_i\)
   • Update the answer candidate: \(\text{ans} = \max(\text{ans}, \text{new\_val})\)
   • Update the value of \(\mathrm{seg}[R_i]\) with \(\text{new\_val}\) (only if it is larger than the existing value)
4. Output the final answer

Complexity

• Time complexity: \(O(N \log T)\)
• Space complexity: \(O(T)\)

Implementation Notes

• Requests must be sorted by end time \(R_i\) before processing

• The segment tree should be built to support range maximum queries, and point updates must be performed with comparison (only updating if the new value is larger)

• During DP updates, past information is used to record the maximum value for the next step, so the processing order is extremely important

  Source Code

import sys
import heapq

input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    T = int(data[1])
    
    meetings = []
    index = 2
    for _ in range(N):
        L = int(data[index])
        R = int(data[index+1])
        V = int(data[index+2])
        meetings.append((L, R, V))
        index += 3
    
    # 区間終端 R でソート
    meetings.sort(key=lambda x: x[1])
    
    # dp[i] := 時間 i までの最大利益
    # セグメント木で高速に取得・更新
    class SegTree:
        def __init__(self, n):
            self.n = n
            self.tree = [0] * (2 * n)
        
        def update(self, i, val):
            i += self.n
            self.tree[i] = val
            while i > 1:
                i //= 2
                self.tree[i] = max(self.tree[2*i], self.tree[2*i+1])
        
        def query(self, l, r):
            res = 0
            l += self.n
            r += self.n
            while l < r:
                if l & 1:
                    res = max(res, self.tree[l])
                    l += 1
                if r & 1:
                    r -= 1
                    res = max(res, self.tree[r])
                l //= 2
                r //= 2
            return res
    
    seg = SegTree(T + 1)
    ans = 0
    
    for L, R, V in meetings:
        # dp[L-1] までの最大値を取得
        max_prev = seg.query(0, L)
        new_val = max_prev + V
        ans = max(ans, new_val)
        # dp[R] を更新
        current = seg.query(R, R+1)
        if new_val > current:
            seg.update(R, new_val)
    
    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.