【題解】Zerojudge j608 - 4. 機器出租

題目連結

題目大意

在有限數量的機器可供租借的情況下，對於 $N$ 個活動，第 $i$ 活動需要在 $[L_i, R_i]$ 的時間段內租借機器才能舉辦。已知每個活動的租借時間段，以及可用的機器數量 $K$，問最多可以成功舉辦多少場活動？

• $1 \leq N \leq 10^5$
• $1 \leq K \leq 100$
• $0 \leq L_i \leq R_i \leq 10^8$

題解

本題與 CSES 的 Movie Festival II 相同，請參考該題的題解。

#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 ，作者 ，並附上原文連結： 【題解】Zerojudge j608 - 4. 機器出租