題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 🔵 P4053 [JSOI2007] 建筑抢修

Problem Statement

題目簡述

有 $N$ 個建築需要修理，每個建築需要 $T_1$ 時間修理，且必須在 $T_2$ 時刻前完成。只有一個工人，一次只能修理一個建築，求最多能修理多少個建築。

Constraints

約束條件

$1 \le N < 150000$
$1 \le T_1 < T_2 < 2^{31}$

思路：反悔貪心

題型定位

反悔貪心模板

先按某個關鍵字排序，邊掃邊維護目前選到的任務。若新任務放不下，但它比已選任務中最耗時的那個更短，就把最耗時的換掉，這就是反悔貪心。

核心目標：在截止時間約束下，最大化完成的任務數量。

從暴力到貪心

如果 $N$ 很小，可以枚舉所有排列，但 $N$ 上限是 $1.5 \times 10^5$ ，這樣的做法無法接受。

先看順序。若已經決定要修理某些建築，那麼按照截止時間從小到大修理一定不會更差。截止時間早的先做，後面截止時間晚的任務仍有較大的緩衝。

排序的正確性

對兩個相鄰任務，若前者截止時間更晚、後者截止時間更早，把它們交換成「早截止先做」不會讓較晚截止的任務更難完成，反而能保護較早截止的任務。因此可以按截止時間升序處理。

排序後，問題變成：依序考慮每個建築，維護一組目前能按時完成的任務。

如何決定選或不選

逐個處理任務時，維護兩個資訊：已選任務的總修理時間，以及一個能快速取得最大修理時間的結構（最大堆）。

能直接容納：若總時間加上當前任務的修理時間，不超過當前任務的截止時間，就直接選它。
不能直接容納：先不要急著丟掉它。若它比已選任務中最耗時的那個更短，就把最耗時的任務換成它。完成數量不變，但總時間變短，後面更容易再塞進新任務。

為什麼不是直接跳過？

直接跳過短任務，等於繼續保留一個更長的任務，總時間只會更大。反悔的目的不是增加當下答案，而是把已選任務「壓短」，替後面的任務留下更多時間。

為何只需比較最大者

只需比較堆中最大值，因為：

若當前任務的時間 ≥ 堆中最大值，替換不會減少總時間，不如保留原選擇。
若當前任務的時間 < 堆中最大值，替換後完成數量不變，但總時間變少，一定更有利。

演算法流程

將所有任務按截止時間升序排序。
維護一個最大堆（Python 中用負值模擬），存放已選任務的修理時間；同時維護已選任務的總時間。
遍歷每個任務：
- 若「總時間 + 當前修理時間 ≤ 截止時間」，選它，將修理時間入堆，更新總時間。
- 否則，若堆非空且堆頂（最大修理時間）大於當前修理時間，則彈出堆頂，改選當前任務，更新總時間。
最終堆的大小即為答案（也是已選任務數量）。

貪心正確性

排序保證先處理更早截止的任務；最大堆保證反悔時總是淘汰最耗時的任務。這樣一來，在完成數量相同的情況下，已選任務的總時間會盡量小，後續就有最多空間繼續加入任務。

複雜度分析

時間複雜度： $\mathcal{O}(N \log N)$ （排序 + 每個任務一次堆操作）
空間複雜度： $\mathcal{O}(N)$ （堆最多存 $N$ 個元素）

Code

from heapq import *

n = int(input())
tasks = [list(map(int, input().split())) for _ in range(n)]
tasks.sort(key=lambda x: x[1])  # 按截止時間升序排序

ans = 0
tot = 0   # 已選任務的總修理時間
hp = []   # 最大堆（用負值模擬），存放已選任務的修理時間
for t1, t2 in tasks:
    if tot + t1 <= t2:          # 可以直接容納
        tot += t1
        ans += 1
        heappush(hp, -t1)
    elif hp and -hp[0] > t1:    # 無法容納，但可以反悔淘汰一個更耗時的任務
        mx = -heappop(hp)
        tot = tot - mx + t1     # 反悔：放棄舊任務，改做當前任務
        heappush(hp, -t1)
print(ans)