j608 - 4. 機器出租

🔗 前往 ZeroJudge 原題

題目描述

題目要求在給定 $N$ 個活動的時間區間 $[L_i, R_i]$ 和 $K$ 台機器的情況下，求最多可以成功舉辦多少場活動。每台機器在同一時間只能租借給一個活動。

解題思路

本題可以使用貪心策略解決。首先，將活動按照結束時間 $R_i$ 升序排序。然後，遍歷排序後的活動列表，對於每個活動，尋找目前空閒時間段最早的機器。如果找到這樣的機器，則將活動分配給該機器，並更新該機器的空閒時間。如果找不到這樣的機器，則跳過該活動。

具體來說，使用一個大小為 $K$ 的數組 b 來記錄每台機器的空閒時間。初始時，將所有機器的空閒時間設置為 -1。遍歷排序後的活動列表，對於每個活動，尋找 b 數組中空閒時間小於活動的開始時間 $L_i$ 且空閒時間最大的機器。如果找到這樣的機器，則將活動分配給該機器，並將該機器的空閒時間更新為活動的結束時間 $R_i$。

複雜度分析

• 時間複雜度: O(N * K + N log N)，其中 N 是活動的數量，K 是機器的數量。排序需要 O(N log N) 的時間，遍歷活動列表需要 O(N) 的時間，在每次遍歷中，尋找空閒時間最早的機器需要 O(K) 的時間。
• 空間複雜度: O(K + N)，其中 N 是活動的數量，K 是機器的數量。需要一個大小為 K 的數組來記錄機器的空閒時間，以及一個大小為 N 的數組來存儲活動信息。

程式碼

#include <iostream>
#include <algorithm>
using namespace std;
long long n,k,b[105],ans;
pair <long long,long long> a[100005];
int main(){
	cin.tie(0); ios::sync_with_stdio(0);
	cin >> n >> k;
	for(int i=0;i<k;++i)b[i]=-1;
	for(int i=0;i<n;++i)
		cin >> a[i].second;
	for(int i=0;i<n;++i)
		cin >> a[i].first;
	sort(a,a+n);
	for(int i=0;i<n;++i){
		int ma=-2,it;
		for(int j=0;j<k;++j){
			if(b[j]<a[i].second&&b[j]>ma){
				ma=b[j];
				it=j;
			}
		}
		if(ma!=-2){
			++ans;
			b[it]=a[i].first;
		}
	}
	cout << ans;
}