概要

この問題は、時間枠ごとに重ならないように会議を選び、得られる利益の合計を最大化する問題です。これは区間スケジューリングの応用であり、動的計画法とセグメント木を用いて効率的に解きます。

考察

まず、素朴な方法として、申請を何らかの順序でソートし、前から貪欲に選ぶことを考えます。しかし、単純に開始時間や終了時間でソートして貪欲に取るだけでは最適解は得られません。なぜなら、各区間に価値（利益 \(V_i\)）があるため、短い区間でも価値が高い場合は選ぶべきだからです。

そこで、「区間スケジューリング＋価値付き」として、終了時刻で昇順にソートした後に動的計画法（DP）を適用する方法を考えます。これは次のようなDPテーブルを定義することで有効になります：

• \(\mathrm{dp}[t] :=\) 時間 \(t\) までに得られる最大利益

しかし、単純な配列によるDPでは、ある申請 \((L_i, R_i, V_i)\) を処理する際に「\(\max_{k=0}^{L_i - 1} \mathrm{dp}[k]\)」を毎回求めると、全体で \(O(N^2)\) となり、制約 \(N \leq 2 \times 10^5\) に対しては間に合いません。

この最大値の取得と更新を高速に行うために、セグメント木などのデータ構造を活用します。特に、区間の最大値の取得と一点更新ができるセグメント木を使えば、各操作が \(O(\log T)\) で行え、全体で十分高速になります。

アルゴリズム

1. 各申請 \((L_i, R_i, V_i)\) を終了時間 \(R_i\) の昇順にソートします。
2. セグメント木を用意し、\(\mathrm{seg}[t] :=\) 時間 \(t\) までを使ったときの最大利益、として管理します。
3. 各申請について：
   • 開始時間より前の時間での最大利益 \(\max_{k=0}^{L_i - 1} \mathrm{seg}[k]\) をセグメント木から取得
   • この申請を使うことで得られる新しい利益を計算：\(\text{new\_val} = \max_{k=0}^{L_i - 1} \mathrm{seg}[k] + V_i\)
   • 答え候補として更新：\(\text{ans} = \max(\text{ans}, \text{new\_val})\)
   • \(\mathrm{seg}[R_i]\) の値を \(\text{new\_val}\) で更新（ただし、既存の値より大きい場合のみ）
4. 最終的な答えを出力

計算量

• 時間計算量: \(O(N \log T)\)
• 空間計算量: \(O(T)\)

実装のポイント

• 申請は必ず終了時間 \(R_i\) でソートしてから処理を行うこと

• セグメント木は区間最大値に対応させて構築し、一点更新も忘れずに比較しながら行うこと

• DPの更新時には、過去の情報を使って次のステップの最大値を記録するという流れになっているため、順番が非常に重要

  ソースコード

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

この解説は qwen3-coder-480b によって生成されました。