題目描述:給定 n 個活動,events[i] = [startDay, endDay],每個活動可在 [startDay, endDay] 中的任意一天參加,但每天最多只能參加一個活動,每個活動只能參加一次。求最多能參加幾個活動。
解題思路:
這是一道需要「貪心 + 最小堆」配合的排程問題。
核心貪心思維:在某一天,如果有多個活動可以選擇,應該優先參加截止日期最早的活動。因為截止日期早的活動如果今天不去,明天可能就錯過了;而截止日期晚的活動明天還有機會。
演算法設計:
複雜度優化:只需遍歷到「最後一個活動的截止日期」,而非無限大。
範例說明:
events = [[1,2],[2,3],[3,4]]
排序:[[1,2],[2,3],[3,4]]
第 1 天:加入截止 2 → 堆 = {2};參加截止 2 的活動 → count = 1
第 2 天:加入截止 3 → 堆 = {3};參加截止 3 的活動 → count = 2
第 3 天:加入截止 4 → 堆 = {4};參加截止 4 的活動 → count = 3
結果:3
時間複雜度:O((n + D) log n) — 其中 D 為最大截止日(最大為 10⁵),n 為活動數量。排序 O(n log n);每個活動最多進堆/出堆一次,各 O(log n);每天最多一次堆操作 O(log n)。整體為 O((n + D) log n)。
空間複雜度:O(n) — 最小堆最多同時儲存 n 個活動的截止日期。
函式 maxEvents(events):
1. 按 events[i][0](開始日)升序排序
2. 建立最小堆 minHeap(按截止日排序)
3. 設 count = 0,i = 0,maxDay = 所有 events[i][1] 的最大值
4. 對 day 從 1 到 maxDay(且 i < n 或堆非空時繼續):
a. 將所有 events[i][0] <= day 的活動之截止日加入 minHeap,i 前進
b. 移除 minHeap 中所有 top() < day 的過期活動
c. 若 minHeap 非空:彈出堆頂(參加截止最早的活動),count 加 1
5. 回傳 count每天遍歷所有未參加的活動,找出今天可以參加且截止日最早的那個。時間複雜度 O(D × n),其中 D 最大為 10⁵,n 最大為 10⁵,共 O(10¹⁰),會超時(TLE)。適合理解思路但不可用於實際提交。
將活動按截止日升序排序,用 multiset 或有序集合記錄每個活動可以被參加的「可用天」。對每個活動,找到 [startDay, endDay] 中最小的可用天參加。此方法思路正確,時間複雜度 O(n log n),但實作較複雜(需要 ordered set 的「找第一個 ≥ start 的元素」操作)。
// 使用 multiset<int> 記錄可用天(1 到 maxDay 都加入)
multiset<int> days;
for (int d = 1; d <= maxDay; d++) days.insert(d);
sort(events.begin(), events.end(), [](auto& a, auto& b){ return a[1] < b[1]; });
for (auto& e : events) {
auto it = days.lower_bound(e[0]);
if (it != days.end() && *it <= e[1]) { count++; days.erase(it); }
}
時間複雜度 O(D + n log n),D 為建立 multiset 的成本。
用線段樹維護每個日期是否被佔用,支援「找第一個可用天」的區間查詢,時間複雜度 O(n log D)。在 D 非常大時比堆方法更優,但實作複雜度高,競賽中較少採用。
Leetcode 1751 — Maximum Number of Events That Can Be Attended II 是本題的進階版:每個活動有價值,最多參加 k 個,求最大總價值。此時貪心不再適用,需要改用 DP + 二分搜尋,時間複雜度 O(n log n × k)。請思考狀態定義和轉移方程。
若每個活動參加後可以獲得不同分數,如何在最多參加 m 個活動的限制下最大化總分? 這是加權版本的區間排程問題,可用 DP 或優先佇列貪心(依分數/時長比值排序)解決,請探討不同策略的適用條件。
本題的最小堆方法與 Dijkstra 演算法中的優先佇列有哪些設計上的相似之處? 兩者都維護一個「最優候選集合」,每次貪心取出當前最優的元素處理,並動態加入新的候選。請嘗試抽象出這種「懶惰評估 + 優先佇列」模式的通用框架,以及它適用的問題類型。