問題描述

在一場電影節中，將播放 n 部電影，Syrjälä 的電影俱樂部有 k 位成員，他們都會參加這場電影節。

你已經知道每部電影的開始與結束時間

每位成員在同一時間只能完整觀看一部電影

請你計算：如果成員們安排得最優化，最多可以完整觀看幾部電影？

練習題

連結：https://cses.fi/problemset/task/1632/

這題我們可以貪婪一點，對於將電影按照開始時間排，維護一個 k 個人看電影的 multiset 存結束時間，若：

  1. 後一部電影開始時間 >= 最早結束的電影，如此原本看那部最早結束電影的人就可以緊接著後一部，並將 ans + 1

  2. 後一部電影開始時間 < 最晚結束的電影，這樣代表讓成員看這部電影比較好，因為越早結束越有可能看更多部，因此可以把目前最晚結束的電影刪除，改成讓那個人看後一部電影，ans 不用加 1 是因為在第一點的時候已經加過了，我們只是替換那個人看的電影，「替換最晚結束的那部」，可以釋放出最多的時間，使未來安排可能性最大化

  • 記得最後要輸出 ans + s.size()，ans 代表看完的電影，s.size() 代表 set 裡還在看電影的成員

完整程式碼

#include <bits/stdc++.h>
using namespace std;
#define ll long long

bool cmp(vector<int> a, vector<int> b) {
    return a[0] < b[0];
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<vector<int>> vec;
    for (int i = 0; i < n; i++) {
        int start, end;
        cin >> start >> end;
        vec.push_back({start, end});
    }
    sort(vec.begin(), vec.end(), cmp);
    int ans = 0;
    multiset<int> s;
    for (int i = 0; i < k; i++) {
        s.insert(vec[i][1]);
    }
    for (int i = k; i < n; i++) {
        int mn = *s.begin();
        int mx = *s.rbegin();
        if (vec[i][0] >= mn) {
            ans++;
            s.erase(s.begin());
            s.insert(vec[i][1]);
        } else if (vec[i][1] < mx) {
            s.erase(prev(s.end()));
            s.insert(vec[i][1]);
        }
    }
    cout << ans + s.size();
}