Day 112-Q2 — Job Sequencing with Deadlines（締切付きジョブスケジューリング）

2026-08-04 赤色 Master / Phase 8+ ★★★★★★★★★ 貪欲法 + Union-Findによる空きスロット高速検索

問題

$N$個のジョブがあり、ジョブ$i$は締切$d_i$と利益$p_i$を持つ。実行には1単位時間かかる。整数スロット$1,2,\dots$の中から締切以下のスロットを1つ選んで割り当てる（1スロットにつき1ジョブ）。スケジュール可能な部分集合の中で利益総和が最大のものを選び、最大利益と選択数を出力せよ。

入力形式

N
d_1 p_1
...
d_N p_N

制約

$1 \le N \le 2\times10^5$
$1 \le d_i \le N$
$1 \le p_i \le 10^9$

入出力例

入力例1

4
2 100
1 19
2 27
1 25

出力例1

127 2

利益100(締切2)をスロット2、利益27(締切2)をスロット1に割り当ててスケジュール可能。合計127、選択数2が最大。

概念図: Union-Findで「空いている最大のスロット」を辿る

利益降順に、find(d)でスロットを確保していく slot0 slot1 slot2 利益100(d=2)→slot2確保 union(2→1) 利益27(d=2)→find(2)=1→slot1確保 利益25,19(d=1)→find(1)=0→割り当て不可

ヒント（段階的開示）

ヒント1: 方向性
利益が高いジョブから貪欲に選び、「締切以下で空いている最も遅いスロット」を探して割り当てたい。毎回線形探索すると$O(N)$で全体$O(N^2)$になる。空きスロット検索を高速化する方法を考える。
ヒント2: アプローチ
利益降順ソート＋交換論法により最適性が証明できる。「$x$以下で使われていない最大のスロット」をUnion-Findで表現し、`find(s)`がその値を返すようにする。スロットを使ったら`union(s,s-1)`。スロット0は番兵（割り当て不可）。
ヒント3: 誘導（コード骨格） 
parent = list(range(N + 1))
def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]
        x = parent[x]
    return x

jobs.sort(key=lambda job: -job.profit)
for d, p in jobs:
    slot = find(d)
    if slot == 0: continue
    total += p; count += 1
    parent[slot] = find(slot - 1)

模範解答 (Python)

import sys

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    jobs = []
    for _ in range(N):
        d = int(data[idx]); idx += 1
        p = int(data[idx]); idx += 1
        jobs.append((d, p))

    parent = list(range(N + 1))

    def find(x):
        root = x
        while parent[root] != root:
            root = parent[root]
        while parent[x] != root:
            parent[x], x = root, parent[x]
        return root

    order = sorted(range(N), key=lambda i: -jobs[i][1])
    total = 0
    count = 0
    for i in order:
        d, p = jobs[i]
        slot = find(d)
        if slot == 0:
            continue
        total += p
        count += 1
        parent[slot] = find(slot - 1)

    print(total, count)

main()
計算量: ソート$O(N\log N)$、Union-Find操作は経路圧縮により償却$O(N\alpha(N))$。全体$O(N\log N)$。全部分集合探索による検証（$N\le8$）と一致することを確認済み。

Step-by-Step 解説

1貪欲法の方針
利益が最大のジョブから順に締切ギリギリのスロットに配置し、早いスロットを後続の低利益ジョブのために温存する。
2「d以下で空いている最大のスロット」をUnion-Findで表現
使用済みスロットのparentは「次に案内すべきスロット」を指す。
3findと経路圧縮
親を根に直接つなぎ替えることで償却計算量を抑える。
4スロットを使ったら1つ前にマージする
parent[slot]=find(slot-1)で以後slotは使用済みとして扱われる。
5全ジョブを利益降順に処理して集計
割り当て可能なら採用し利益と個数を加算する。

よくあるミス

ミス原因正しい書き方
締切の昇順でソートしてしまう「早く終わるものを優先」という直感に引っ張られる貪欲法の正当性は利益の降順に依存する
スロット0の番兵を用意し忘れるfind(d)が0になるケースの判定を設計していないparent配列を0..Nで確保しfind(x)==0を割り当て不可の判定に使う
経路圧縮を使わず直接更新する一見動くが最悪ケースでfindがO(N)かかるparent[slot]=find(slot-1)として圧縮済み代表に直接つなぐ
締切がNより大きい入力を想定して配列サイズを固定する制約$d_i\le N$を見落とす制約を確認しparent配列を締切の最大値に合わせて確保する

次のステップ

  • 発展: ジョブの実行時間が可変長の場合への拡張（Weighted Interval Schedulingとの比較）
  • 発展: 開始可能時刻も持つジョブへの拡張と他の貪欲構造との比較
  • 発展: オンラインでジョブが逐次到着する設定への変更

自己評価

自分の回答

気づき・メモ