贪心
如果能让所有客人满意,那么在 di 时间就只能接待第 i 个客人,并在此之前完成该订单的准备,因此 di 就是任务的优先级。需要对 (si, di, ci) 数组按 di 从大到小排序.
另外,越紧急的任务越要先处理。在 si 时间收到订单 (si, di, ci) 时就需要尽快准备该订单。可以证明这样的策略是最优的。
假设有两个订单 (si, di, ci) 和 (sj, dj, cj), di < dj
若 si < sj, 如果不先准备订单 i, 那么 si 到 sj 这段时间就是浪费的。
若 si >= sj, 如果在 si 之后还是处理订单 j, 那么订单 i 可能会完不成,而订单 j 可以在 si 之前处理以及准备完订单 i 之后再处理。
时间复杂度 O(mlogn)
使用一个 set 维护每个时间段
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int n, m;
struct info {
int s, d, c, id;
} nums[N];
int ans[N];
set<int> st;
int main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
cin >> n >> m;
for(int i = 1; i <= n; i++) st.insert(i);
for(int i = 1; i <= m; i++) {
cin >> nums[i].s >> nums[i].d >> nums[i].c;
nums[i].id = i;
st.erase(nums[i].d);
ans[nums[i].d] = m + 1;
}
sort(nums + 1, nums + 1 + m, [&](const info& a, const info& b) -> bool {
return a.d < b.d;
});
for(int i = 1; i <= m; i++) {
int s = nums[i].s, d = nums[i].d, c = nums[i].c, id = nums[i].id;
auto it = st.lower_bound(s); // 寻找该任务最早可以开始的时间
while(c) {
if(it == st.end()) {
cout << -1 << '\n';
return 0;
}
int p = *it;
if(p >= d) { // 不能超过客人到访时间
cout << -1 << '\n';
return 0;
}
ans[p] = id;
it = st.erase(it);
c -= 1;
}
}
for(int i = 1; i <= n; i++)
cout << ans[i] << ' ';
return 0;
}