Day 004-Q5 | 優先度付きキュー

問題

タスクスケジューリング。N個のタスクに締め切り d[i] と報酬 p[i]。各タスクは1日かかる。1〜max_d の日程の中で、締め切りまでに終わるよう1日1タスク選んで実行したとき、獲得できる報酬の最大値を求めよ。

入力形式

N
d[0] p[0]
...
d[N-1] p[N-1]

制約

$1 \le N \le 2 \times 10^5$

$1 \le d_i \le 2 \times 10^5$

$1 \le p_i \le 10^9$

入出力例

入力例 1

出力例 1

Day1: 200, Day2: 150, Day3: 100 = 450

ヒント (段階的開示)

ヒント1: 方向性

「締め切りを守りながら報酬最大化」→ 貪欲 + 優先度付きキュー（最大ヒープ）。

ヒント2: アプローチ

締め切り昇順にソート → 各日付で「その日までに開始できるタスク」をヒープに追加 → 最大報酬を1つ実行。

ヒント3: 誘導

import heapq
tasks.sort()
heap = []
task_idx = 0
for day in range(1, max_d + 1):
    while task_idx < N and tasks[task_idx][0] <= day:
        heapq.heappush(heap, -tasks[task_idx][1])
        task_idx += 1
    if heap:
        total += -heapq.heappop(heap)

模範解答 (Python)

import heapq
import sys
input = sys.stdin.readline

def solve():
    N = int(input())
    tasks = []
    max_d = 0
    for _ in range(N):
        d, p = map(int, input().split())
        tasks.append((d, p))
        max_d = max(max_d, d)

    tasks.sort()

    heap = []
    task_idx = 0
    total = 0

    for day in range(1, max_d + 1):
        while task_idx < N and tasks[task_idx][0] <= day:
            heapq.heappush(heap, -tasks[task_idx][1])
            task_idx += 1

        if heap:
            total += -heapq.heappop(heap)

    print(total)

solve()

Step-by-Step 解説

1Python の heapq は最小ヒープ
最大ヒープを実現するには負値を格納 → heappush(heap, -p)。

2貪欲の根拠
「今日が締め切りのタスク群の中で最大の報酬を選ぶ」を各日付で繰り返す。

計算量

ソート: $O(N \log N)$
ヒープ操作: $O(N \log N)$
全体: $O((N + \max d) \log N)$

よくあるミス

ミス	原因	正しい書き方
最小ヒープのまま	Python heapq は最小	負値で最大ヒープに
締め切り条件の方向間違い	`day <= d[i]` を逆に	`tasks[task_idx][0] <= day`
max_d を大きく取りすぎ	全日付ループ → TLE	N + max_d で工夫

Day 004-Q5 — 優先度付きキュー

問題