Day 153-Q3 | 重み付き区間スケジューリング

問題

$N$ 件のジョブが与えられる。ジョブ $i$ は開始時刻 $s_i$、終了時刻 $e_i$（$s_i<e_i$）、重み $w_i$ を持つ。2つのジョブ $i,j$ が「両立する」とは、区間として重ならないこと（$e_i\le s_j$ または $e_j\le s_i$、端点が一致するのは両立とみなす）を指す。

互いに両立するジョブの部分集合を選び、重みの総和を最大化せよ。

入力形式

N
s_1 e_1 w_1
s_2 e_2 w_2
:
s_N e_N w_N

制約

$1 \le N \le 2000$

$1 \le s_i < e_i \le 10^9$

$1 \le w_i \le 10^9$

入出力例

入力例1

出力例1

概念図：タイムラインと採用ジョブ

ヒント（段階的開示）

ヒント1（方向性）

「重みが大きい順」も「早く終わる順」も貪欲に選ぶと重み付きの場合は最適解を出せない反例が作れる（本問題の入力例1で重み最大のJob2だけ選ぶと6にしかならないが、正解は14）。貪欲法を捨ててDPに切り替える必要がある。

ヒント2（アプローチ）

ジョブを終了時刻 $e_i$ の昇順にソートし、$dp[i]=\max(dp[i-1], w_i+dp[p(i)])$ とする。$p(i)$は「ジョブ$i$と両立する（$e_j\le s_i$）ジョブの中で最も番号が大きいもの」で、$e$が昇順ソート済みなので二分探索（`bisect_right`）で$O(\log N)$。

ヒント3（誘導）

import bisect

jobs.sort(key=lambda x: x[1])
ends = [job[1] for job in jobs]
dp = [0] * (n + 1)
for i in range(1, n + 1):
    s, e, w = jobs[i - 1]
    p = bisect.bisect_right(ends, s, 0, i - 1)
    dp[i] = max(dp[i - 1], w + dp[p])
print(dp[n])

模範解答 (Python)

import sys
import bisect


def main():
    input_data = sys.stdin.read().split()
    idx = 0
    n = int(input_data[idx]); idx += 1
    jobs = []
    for _ in range(n):
        s = int(input_data[idx]); e = int(input_data[idx + 1]); w = int(input_data[idx + 2])
        idx += 3
        jobs.append((s, e, w))

    jobs.sort(key=lambda x: x[1])
    ends = [job[1] for job in jobs]

    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        s, e, w = jobs[i - 1]
        p = bisect.bisect_right(ends, s, 0, i - 1)
        dp[i] = max(dp[i - 1], w + dp[p])

    print(dp[n])


main()

Step-by-Step 解説

1終了時刻でソート
入力例1は既に$e$昇順（1,3,5→2,5,6→4,6,5→6,7,4）。`ends=[3,5,6,7]`。

2各ジョブの p(i) を二分探索
$p(1)=0,p(2)=0,p(3)=1,p(4)=3$。

3DPを埋める
$dp[1]=5,dp[2]=6,dp[3]=10,dp[4]=14$。出力例1の14と一致（Job1+Job3+Job4=5+5+4）。

4なぜ貪欲法ではダメか
重み最大優先だとJob2(重み6)だけ選び、他が全て重なって選べず6止まり。DPは選ぶ/選ばないの両方を厳密比較するため局所最適に惑わされない。

よくあるミス

ミス	原因	正しい書き方
重み最大/終了最速の貪欲法で解こうとする	本数最大化と重み最大化を混同	重み付きは必ずDP
`bisect_left`を使う	端点一致($e_j=s_i$)を両立扱いできない	`bisect_right(ends, s)`が正しい
ソート前のインデックスのままp(i)を使う	並び替え後とのズレ	ソート後の配列で一貫してインデックスを扱う
`max`を取り忘れる	「選ばない」選択肢を考慮しない	必ず`max(dp[i-1], w_i+dp[p(i)])`
時刻の値でDP配列を作ろうとする	$s_i,e_i\le10^9$を添字と誤解	DPの添字はジョブ数$N$の範囲で持つ

次のステップ

発展: $K$台のマシンに割り当てて良い場合（K-machine scheduling）に拡張し、優先度付きキューで各マシンの空き時刻を管理する。
次回予告: 関数グラフ上のダブリング（Binary Lifting on Functional Graph）

自己評価

完全理解おおむね理解要復習

Day 153-Q3 — 重み付き区間スケジューリング（Weighted Interval Scheduling）

問題