【題解】CSES - Movie Festival II

題目連結

題目大意

給定 $n$ 個電影開始和結束的時間 $a_i$ 和 $b_i$，問 $k$ 個人最多可以看幾種不同的電影？

• $1 \leq k \leq n \leq 2 \cdot 10^5$
• $1 \leq a < b \leq 10^9$

題解

與 Movie Festival 非常類似，只不過這題多了 $k$ 的變數。與該題相同用 greedy，我們將時間段按照右界由小到大排序。假設當前的時刻第 $j$ 個機器結束的時間為 $t_j$，則我們將當前活動 $i$ 分配給最晚結束且 $t_j < L_i$，並更新該機器結束的時間。這個 greedy 正確性的證明留給讀者練習。實作的細節請參考 code。

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, k;
	cin >> n >> k;
	vector<int> l(n), r(n);
	for(int i = 0; i < n; ++i) {
		cin >> l[i];
	}
	for(int i = 0; i < n; ++i) {
		cin >> r[i];
	}
	vector<int> ord(n);
	iota(ord.begin(), ord.end(), 0);
	sort(ord.begin(), ord.end(), [&](int i, int j) {
		return r[i] < r[j];
	});
	multiset<int> end;
	for(int i = 0; i < k; ++i) {
		end.insert(end.end(), -1);
	}
	int ans = 0;
	for(auto id : ord) {
		auto it = end.lower_bound(l[id]);
		if(it == end.begin()) {
			continue;
		}
		ans++;
		end.erase(prev(it));
		end.insert(r[id]);
	}
	cout << ans << "\n";
	return 0;
}

如果本文對您有幫助的話幫忙點擊廣告和分享吧！

© 若無特別註明，本站文章皆由 WeakMouse's Coding Blog 原創 ，轉載引用本文前請先留言告知。本文轉載請註明文章源自 WeakMouse's Coding Blog ，作者 ，並附上原文連結： 【題解】CSES - Movie Festival II