🔗 CSES-1632 Movie Festival II

Problem Statement

題目簡述

有 nn 部電影與 kk 位社團成員，每部電影都有開始時間與結束時間。每位成員同一時間只能完整觀看一部電影，若前一部電影的結束時間不晚於下一部電影的開始時間，則可以接續觀看。

請問在所有成員都最佳安排的情況下，最多總共可以完整觀看幾部電影。

Constraints

約束條件

  • 1≤k≤n≤2⋅1051 \le k \le n \le 2 \cdot 10^5
  • 1≤a<b≤1091 \le a < b \le 10^9

思路：按結束時間貪心安排

這題是經典活動選擇問題的推廣：把一條時間線換成 kk 條。

活動選擇問題的多人版本

當 k=1k = 1 時，就是標準活動選擇問題：按結束時間排序後，貪心地選取不重疊區間。交換論證可證最優。
本題只是多了 kk 條獨立的時間線，每條線上仍然不能重疊。

貪心策略的核心沒變：電影仍然按結束時間遞增排序，越早結束的越優先考慮。變化的是——每部電影到底要讓誰看？

不妨維護各成員「目前看完最後一部電影的結束時間」。初始 kk 位成員都還沒看，結束時間全為 00。

對當前電影來說，能接上的人必須滿足：該成員的結束時間不超過電影的開始時間。但如果多個人都能接，要挑誰？

關鍵貪心

在能接上的人中，選**結束時間最晚（但仍不超過開始時間）**的那位。

理由是：結束時間越晚的人，之後能接的電影越少，所以優先消耗掉；結束時間更早的人空檔更長、更靈活，留待後面更難安排的場合使用。
若反過來選結束最早的人，等於讓本來就很靈活的人去處理當前電影，浪費了那份靈活性。

如果所有人的結束時間都已經超過當前開始時間，代表沒人能抽身來看這一部，直接跳過。

方法一：有序容器維護

用平衡樹（如 multiset）維護 kk 位成員當前的結束時間。

對每部電影：在平衡樹中二分求出最後一個不超過開始時間的值。若存在，刪除該值、插入當前電影的結束時間，答案加一；否則跳過。

複雜度分析

  • 時間複雜度：O(nlog⁡n+nlog⁡k)\mathcal{O}(n \log n + n \log k)，排序一次 O(nlog⁡n)\mathcal{O}(n \log n)，每部電影一次平衡樹查詢與更新 O(log⁡k)\mathcal{O}(\log k)
  • 空間複雜度：O(n+k)\mathcal{O}(n + k)，儲存電影陣列與 kk 位成員的平衡樹節點

方法二：區間併查集維護

回看方法一的平衡樹插入：因為電影是按結束時間遞增處理的，成功安排後加入的新結束時間也是非遞減的。換句話說，新值永遠只會出現在尾端，不需要在中間插入。

為什麼可以只往尾端追加？

因為電影按結束時間遞增處理。成功安排的電影，其結束時間一定不小於之前任何一個被安排電影的結束時間。所以新值天然就會落在陣列尾端，不會插入中間破壞有序性。

這意味著可以把平衡樹換成普通陣列：初始放入 kk 個 00，每次成功安排就把當前電影的結束時間推到尾端。陣列全程保持有序。

現在對當前電影：

  1. 用二分找出陣列中最後一個不超過開始時間的位置
  2. 在 [1, 該位置][1,\, \text{該位置}] 的範圍內，找到最靠右且還沒被用掉的位置

找到的位置若大於 00，就標記為已用，並將當前電影的結束時間追加到尾端。

用併查集維護「可用位置」

陣列每個位置對應一個「可能的結束時間值」。用掉某個位置後，透過併查集將它合併到左邊，之後再查到這裡時會自動跳到左邊最近的仍可用位置。

這本質上是「區間併查集」手法：每個位置被佔用後指向上一個可用後繼，查詢時路徑壓縮一氣呵成。

複雜度分析

  • 時間複雜度：O(nlog⁡n)\mathcal{O}(n \log n)，排序一次 O(nlog⁡n)\mathcal{O}(n \log n)，每部電影一次二分 O(log⁡n)\mathcal{O}(\log n)，併查集操作均攤近似常數
  • 空間複雜度：O(n+k)\mathcal{O}(n + k)，儲存電影陣列、結束時間陣列與併查集父節點陣列

Code

方法一：有序容器維護結束時間

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
#include <ranges>
using namespace std;
#define endl '\n'

void solve() {
    int n, k;
    cin >> n >> k;
    vector<pair<int, int>> movies(n);
    for (auto& [s, e] : movies) cin >> s >> e;

    ranges::sort(movies, [](auto& a, auto& b) { return a.second < b.second; });

    multiset<int> ends;
    for (int i = 0; i < k; i++) ends.insert(0);

    int ans = 0;
    for (auto& [s, e] : movies) {
        auto it = ends.upper_bound(s);
        if (it == ends.begin()) continue;
        ends.erase(--it);
        ends.insert(e);
        ans++;
    }
    cout << ans << endl;
    return;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

方法二：區間併查集維護

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
from bisect import bisect_right


def solve():
    n, k = map(int, input().split())
    movies = [tuple(map(int, input().split())) for _ in range(n)]
    movies.sort(key=lambda x: x[1])

    ans = 0
    ends = [0] * k
    fa = list(range(n + k + 1))  # 1-indexed DSU

    def find(x: int) -> int:
        while fa[x] != x:
            fa[x] = fa[fa[x]]
            x = fa[x]
        return x

    for l, r in movies:
        idx = bisect_right(ends, l)
        idx = find(idx)
        if idx > 0:
            fa[idx] = find(idx - 1)  # 向左合併
            ends.append(r)
            ans += 1

    print(ans)


if __name__ == "__main__":
    solve()