概要

互いに時間が重ならないように会議の申請を選び、利益の合計を最大化する問題です。これは「重み付き区間スケジューリング問題（Weighted Interval Scheduling）」として知られる典型問題で、動的計画法（DP）と二分探索を組み合わせて効率的に解くことができます。

考察

重要な気づき

まず、各会議は区間 \([L_i, R_i]\) を占有し、重なる区間同士は同時に選べません。利益 \(V_i\) が会議ごとに異なるため、単に「たくさん選ぶ」のではなく「利益の合計が最大になるように選ぶ」必要があります。

素朴なアプローチとその問題点

素朴に考えると、\(N\) 件の申請それぞれについて「承認する/しない」の \(2\) 通りを試す全探索が思い浮かびます。しかし、これでは \(O(2^N)\) 通りの組み合わせを調べることになり、\(N \leq 2 \times 10^5\) では到底間に合いません。

解決の方針

会議を終了時刻の早い順にソートして、DPを適用します。

会議を終了時刻順に並べると、「\(i\) 番目の会議を選ぶなら、その前に選べるのは終了時刻が \(L_i - 1\) 以下の会議だけ」という構造が見えます。この「\(L_i - 1\) 以下で最後に終わる会議」は、ソート済みの終了時刻に対して二分探索で高速に求められます。

アルゴリズム

1. ソート: \(N\) 件の会議を終了時刻 \(R_i\) の昇順にソートする。

2. DP の定義: \(dp[i]\) を「ソート後の最初の \(i\) 件の会議だけを候補としたときの最大利益」とする。初期値は \(dp[0] = 0\)。

3. 遷移: \(i\) 番目の会議（0-indexed）について、次の2つの選択肢の大きい方を取る。

   • \(i\) 番目を選ばない場合: \(dp[i+1] = dp[i]\)
   • \(i\) 番目を選ぶ場合: \(i\) 番目の会議の開始時刻 \(L_i\) より前に終わる会議のうち、最も後ろのもの（インデックス \(j\)）を二分探索で見つけ、\(dp[i+1] = dp[j] + V_i\)

すなわち: $\(dp[i+1] = \max(dp[i],\; dp[j] + V_i)\)\( ここで \)j\( は、終了時刻が \)L_i - 1\( 以下である会議の数（= ソート後の配列で終了時刻 \)\leq L_i - 1\( を満たす最大インデックス \)+1$）です。

1. 答え: \(dp[N]\) を出力する。

具体例

例えば、3件の会議が以下のように与えられたとします：

会議	\(L\)	\(R\)	\(V\)
A	1	3	10
B	2	5	8
C	4	6	12

終了時刻順にソートすると A → B → C。

• \(dp[0] = 0\)
• 会議A (\(R=3, L=1, V=10\)): \(L-1=0\) 以下に終わる会議はない（\(j=0\)）。\(dp[1] = \max(0, 0+10) = 10\)
• 会議B (\(R=5, L=2, V=8\)): \(L-1=1\) 以下に終わる会議はない（\(j=0\)）。\(dp[2] = \max(10, 0+8) = 10\)
• 会議C (\(R=6, L=4, V=12\)): \(L-1=3\) 以下に終わる会議はA（\(j=1\)）。\(dp[3] = \max(10, 10+12) = 22\)

答えは \(22\)（会議AとCを選択）。

計算量

• 時間計算量: \(O(N \log N)\)（ソートに \(O(N \log N)\)、各会議に対する二分探索に \(O(\log N)\)）
• 空間計算量: \(O(N)\)（会議リスト・DP配列の格納）

実装のポイント

• 終了時刻でソートすることがこのアルゴリズムの前提です。ソートを忘れると正しい結果になりません。

• 二分探索では、「終了時刻が \(L_i - 1\) 以下」の会議を探します。Pythonの bisect_right(ends, L_i - 1, 0, i) は、ends[0:i] の中で \(L_i - 1\) より大きい最初の位置を返すので、それがそのまま「条件を満たす会議の個数 \(j\)」（= DP のインデックス）となります。

• \(dp\) 配列は1-indexedで管理し、\(dp[0] = 0\)（何も選ばない状態）を基底とすると、遷移が自然に書けます。

  ソースコード

import sys
from bisect import bisect_right

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    T = int(input_data[idx]); idx += 1
    
    meetings = []
    for i in range(N):
        L = int(input_data[idx]); idx += 1
        R = int(input_data[idx]); idx += 1
        V = int(input_data[idx]); idx += 1
        meetings.append((R, L, V))
    
    # Sort by end time
    meetings.sort()
    
    # ends[i] = end time of i-th meeting (0-indexed, sorted)
    ends = [m[0] for m in meetings]
    
    # dp[i] = max profit considering first i meetings (1-indexed)
    # dp[0] = 0
    dp = [0] * (N + 1)
    
    for i in range(N):
        R, L, V = meetings[i]
        # Find the latest meeting that ends before L (i.e., end <= L-1)
        # We need the largest j such that ends[j] <= L-1, j < i
        j = bisect_right(ends, L - 1, 0, i)
        # j is the number of meetings among first i that end <= L-1
        dp[i + 1] = max(dp[i], dp[j] + V)
    
    print(dp[N])

main()

---

この解説は claude4.6opus-thinking によって生成されました。