class Solution {
public:
int findCrossingTime(int n, int k, vector<vector<int>>& time) {
}
};
6306. 过桥的时间
共有 k 位工人计划将 n 个箱子从旧仓库移动到新仓库。给你两个整数 n 和 k，以及一个二维整数数组 time ，数组的大小为 k x 4 ，其中 time[i] = [leftToRighti, pickOldi, rightToLefti, putNewi] 。
一条河将两座仓库分隔，只能通过一座桥通行。旧仓库位于河的右岸，新仓库在河的左岸。开始时，所有 k 位工人都在桥的左侧等待。为了移动这些箱子，第 i 位工人（下标从 0 开始）可以：
leftToRighti 分钟。pickOldi 分钟。不同工人可以同时搬起所选的箱子。rightToLefti 分钟。putNewi 分钟。不同工人可以同时放下所选的箱子。如果满足下面任一条件，则认为工人 i 的 效率低于 工人 j ：
leftToRighti + rightToLefti > leftToRightj + rightToLeftjleftToRighti + rightToLefti == leftToRightj + rightToLeftj 且 i > j工人通过桥时需要遵循以下规则：
x 到达桥边时，工人 y 正在过桥，那么工人 x 需要在桥边等待。所有 n 个盒子都需要放入新仓库，请你返回最后一个搬运箱子的工人 到达河左岸 的时间。
示例 1：
输入：n = 1, k = 3, time = [[1,1,2,1],[1,1,3,1],[1,1,4,1]] 输出：6 解释： 从 0 到 1 ：工人 2 从左岸过桥到达右岸。 从 1 到 2 ：工人 2 从旧仓库搬起一个箱子。 从 2 到 6 ：工人 2 从右岸过桥到达左岸。 从 6 到 7 ：工人 2 将箱子放入新仓库。 整个过程在 7 分钟后结束。因为问题关注的是最后一个工人到达左岸的时间，所以返回 6 。
示例 2：
输入：n = 3, k = 2, time = [[1,9,1,8],[10,10,10,10]] 输出：50 解释： 从 0 到 10 ：工人 1 从左岸过桥到达右岸。 从 10 到 20 ：工人 1 从旧仓库搬起一个箱子。 从 10 到 11 ：工人 0 从左岸过桥到达右岸。 从 11 到 20 ：工人 0 从旧仓库搬起一个箱子。 从 20 到 30 ：工人 1 从右岸过桥到达左岸。 从 30 到 40 ：工人 1 将箱子放入新仓库。 从 30 到 31 ：工人 0 从右岸过桥到达左岸。 从 31 到 39 ：工人 0 将箱子放入新仓库。 从 39 到 40 ：工人 0 从左岸过桥到达右岸。 从 40 到 49 ：工人 0 从旧仓库搬起一个箱子。 从 49 到 50 ：工人 0 从右岸过桥到达左岸。 从 50 到 58 ：工人 0 将箱子放入新仓库。 整个过程在 58 分钟后结束。因为问题关注的是最后一个工人到达左岸的时间，所以返回 50 。
提示：
1 <= n, k <= 104time.length == ktime[i].length == 41 <= leftToRighti, pickOldi, rightToLefti, putNewi <= 1000原站题解
cpp 解法, 执行用时: 132 ms, 内存消耗: 22.4 MB, 提交时间: 2023-01-09 10:51:11
class Solution {
public:
int findCrossingTime(int n, int K, vector<vector<int>>& time) {
typedef pair<long long, int> pli;
// 所有工人按效率从高到低排序
// 因为不需要输出和工人下标有关系的东西，排序后下标的顺序就是效率顺序，比较方便
for (int i = 0; i < K; i++) time[i].push_back(i);
sort(time.begin(), time.end(), [](vector<int> &a, vector<int> &b) {
int L = a[0] + a[2], R = b[0] + b[2];
if (L != R) return L < R;
else return a[4] < b[4];
});
// now：桥接下来的可用时间
long long now = 0;
// 用大根堆模拟效率低的工人先过桥
// left：左边目前有哪些工人等待过桥
// right：右边目前有哪些工人等待过桥
priority_queue<int> left, right;
// 用小根堆模拟哪些工人先放好箱子
// pL：左边有哪些工人正在放箱子
// pR：右边有哪些工人正在拿箱子
// 这个 pair 中，第一个数是工人放（拿）好箱子的时间，第二个数是工人的编号
priority_queue<pli, vector<pli>, greater<pli>> pL, pR;
// 一开始所有工人都在左边等待
for (int i = 0; i < K; i++) left.push(i);
// 模拟搬运过程
while (true) {
// 桥接下来的可用时间到来前，哪些工人已经放好箱子了，把他们加入等待队列
while (!pL.empty()) {
pli p = pL.top();
if (p.first > now) break;
pL.pop();
left.push(p.second);
}
while (!pR.empty()) {
pli p = pR.top();
if (p.first > now) break;
pR.pop();
right.push(p.second);
}
// 判断桥接下来的可用时间到来后，左右是否有人可以过桥
bool leftGo = n > 0 && !left.empty();
bool rightGo = !right.empty();
if (!leftGo && !rightGo) {
// 左右都没有人可以过桥，直接快进到下一个有人过桥的时间
long long x = 1e18;
if (!pL.empty()) x = min(x, pL.top().first);
if (!pR.empty()) x = min(x, pR.top().first);
now = x;
continue;
}
if (rightGo) {
// 右边有人要过桥
int x = right.top(); right.pop();
now += time[x][2];
// 已经没有箱子可以搬了，而且右边也没人等着过桥，可以返回答案
if (n == 0 && right.empty() && pR.empty()) return now;
// 把过桥的人加入放箱子的优先队列
pL.push(pli(now + time[x][3], x));
} else {
// 左边有人要过桥
int x = left.top(); left.pop();
now += time[x][0];
// 拿走一个箱子
n--;
// 把过桥的人加入拿箱子的优先队列
pR.push(pli(now + time[x][1], x));
}
}
}
};
java 解法, 执行用时: 47 ms, 内存消耗: 48.5 MB, 提交时间: 2023-01-09 10:50:42
class Solution {
public int findCrossingTime(int n, int k, int[][] time) {
Arrays.sort(time, (a, b) -> a[0] + a[2] - b[0] - b[2]); // 稳定排序
var workL = new PriorityQueue<int[]>((a, b) -> a[1] - b[1]);
var workR = new PriorityQueue<int[]>(workL.comparator());
var waitL = new PriorityQueue<int[]>((a, b) -> b[0] - a[0]); // 下标越大效率越低
var waitR = new PriorityQueue<int[]>(waitL.comparator());
for (int i = k - 1; i >= 0; --i) waitL.add(new int[]{i, 0});
int cur = 0;
while (n > 0) {
while (!workL.isEmpty() && workL.peek()[1] <= cur) waitL.add(workL.poll()); // 左边完成放箱
while (!workR.isEmpty() && workR.peek()[1] <= cur) waitR.add(workR.poll()); // 右边完成搬箱
if (!waitR.isEmpty()) { // 右边过桥，注意加到 waitR 中的都是 <= cur 的（下同）
var p = waitR.poll();
cur += time[p[0]][2];
p[1] = cur + time[p[0]][3];
workL.add(p); // 放箱
} else if (!waitL.isEmpty()) { // 左边过桥
var p = waitL.poll();
cur += time[p[0]][0];
p[1] = cur + time[p[0]][1];
workR.add(p); // 搬箱
--n;
} else if (workL.isEmpty()) cur = workR.peek()[1]; // cur 过小，找个最小的放箱/搬箱完成时间来更新 cur
else if (workR.isEmpty()) cur = workL.peek()[1];
else cur = Math.min(workL.peek()[1], workR.peek()[1]);
}
while (!workR.isEmpty()) {
var p = workR.poll(); // 右边完成搬箱
// 如果没有排队，直接过桥；否则由于无论谁先过桥，最终完成时间都一样，所以也可以直接计算
cur = Math.max(p[1], cur) + time[p[0]][2];
}
return cur; // 最后一个过桥的时间
}
}
cpp 解法, 执行用时: 140 ms, 内存消耗: 21.8 MB, 提交时间: 2023-01-09 10:50:23
class Solution {
public:
int findCrossingTime(int n, int k, vector<vector<int>> &time) {
stable_sort(time.begin(), time.end(), [](auto &a, auto &b) {
return a[0] + a[2] < b[0] + b[2];
});
priority_queue<pair<int, int>> waitL, waitR;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> workL, workR;
for (int i = k - 1; i >= 0; --i) waitL.emplace(i, 0); // 下标越大效率越低
int cur = 0;
while (n) {
while (!workL.empty() && workL.top().first <= cur) {
auto[t, i] = workL.top();
workL.pop();
waitL.emplace(i, t); // 左边完成放箱
}
while (!workR.empty() && workR.top().first <= cur) {
auto[t, i] = workR.top();
workR.pop();
waitR.emplace(i, t); // 右边完成搬箱
}
if (!waitR.empty()) { // 右边过桥，注意加到 waitR 中的都是 <= cur 的（下同）
auto[i, t] = waitR.top();
waitR.pop();
cur += time[i][2];
workL.emplace(cur + time[i][3], i); // 放箱
} else if (!waitL.empty()) { // 左边过桥
auto[i, t] = waitL.top();
waitL.pop();
cur += time[i][0];
workR.emplace(cur + time[i][1], i); // 搬箱
--n;
} else if (workL.empty()) cur = workR.top().first; // cur 过小，找个最小的放箱/搬箱完成时间来更新 cur
else if (workR.empty()) cur = workL.top().first;
else cur = min(workL.top().first, workR.top().first);
}
while (!workR.empty()) {
auto[t, i] = workR.top(); // 右边完成搬箱
workR.pop();
// 如果没有排队，直接过桥；否则由于无论谁先过桥，最终完成时间都一样，所以也可以直接计算
cur = max(t, cur) + time[i][2];
}
return cur; // 最后一个过桥的时间
}
};
golang 解法, 执行用时: 116 ms, 内存消耗: 7.8 MB, 提交时间: 2023-01-09 10:50:03
func findCrossingTime(n, k int, time [][]int) (cur int) {
sort.SliceStable(time, func(i, j int) bool {
a, b := time[i], time[j]
return a[0]+a[2] < b[0]+b[2]
})
waitL, waitR := make(hp, k), hp{}
for i := range waitL {
waitL[i].i = k - 1 - i // 下标越大效率越低
}
workL, workR := hp2{}, hp2{}
for n > 0 {
for len(workL) > 0 && workL[0].t <= cur {
heap.Push(&waitL, heap.Pop(&workL)) // 左边完成放箱
}
for len(workR) > 0 && workR[0].t <= cur {
heap.Push(&waitR, heap.Pop(&workR)) // 右边完成搬箱
}
if len(waitR) > 0 { // 右边过桥，注意加到 waitR 中的都是 <= cur 的（下同）
p := heap.Pop(&waitR).(pair)
cur += time[p.i][2]
heap.Push(&workL, pair{p.i, cur + time[p.i][3]}) // 放箱，记录完成时间
} else if len(waitL) > 0 { // 左边过桥
p := heap.Pop(&waitL).(pair)
cur += time[p.i][0]
heap.Push(&workR, pair{p.i, cur + time[p.i][1]}) // 搬箱，记录完成时间
n--
} else if len(workL) == 0 { // cur 过小，找个最小的放箱/搬箱完成时间来更新 cur
cur = workR[0].t
} else if len(workR) == 0 {
cur = workL[0].t
} else {
cur = min(workL[0].t, workR[0].t)
}
}
for len(workR) > 0 {
p := heap.Pop(&workR).(pair) // 右边完成搬箱
// 如果没有排队，直接过桥；否则由于无论谁先过桥，最终完成时间都一样，所以也可以直接计算
cur = max(p.t, cur) + time[p.i][2]
}
return cur // 最后一个过桥的时间
}
type pair struct{ i, t int }
type hp []pair
func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].i > h[j].i }
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v interface{}) { *h = append(*h, v.(pair)) }
func (h *hp) Pop() interface{} { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
type hp2 []pair
func (h hp2) Len() int { return len(h) }
func (h hp2) Less(i, j int) bool { return h[i].t < h[j].t }
func (h hp2) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp2) Push(v interface{}) { *h = append(*h, v.(pair)) }
func (h *hp2) Pop() interface{} { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
func min(a, b int) int { if b < a { return b }; return a }
func max(a, b int) int { if b > a { return b }; return a }
python3 解法, 执行用时: 284 ms, 内存消耗: 19.3 MB, 提交时间: 2023-01-09 10:49:34
class Solution:
def findCrossingTime(self, n: int, k: int, time: List[List[int]]) -> int:
time.sort(key=lambda t: t[0] + t[2]) # 稳定排序
cur = 0
workL, waitL, waitR, workR = [], [[-i, 0] for i in range(k - 1, -1, -1)], [], [] # 下标越大效率越低
while n:
while workL and workL[0][0] <= cur:
p = heappop(workL)
p[0], p[1] = p[1], p[0]
heappush(waitL, p) # 左边完成放箱
while workR and workR[0][0] <= cur:
p = heappop(workR)
p[0], p[1] = p[1], p[0]
heappush(waitR, p) # 右边完成搬箱
if waitR: # 右边过桥，注意加到 waitR 中的都是 <= cur 的（下同）
p = heappop(waitR)
cur += time[-p[0]][2]
p[1] = p[0]
p[0] = cur + time[-p[0]][3]
heappush(workL, p) # 放箱
elif waitL: # 左边过桥
p = heappop(waitL)
cur += time[-p[0]][0]
p[1] = p[0]
p[0] = cur + time[-p[0]][1]
heappush(workR, p) # 搬箱
n -= 1
elif len(workL) == 0: cur = workR[0][0] # cur 过小，找个最小的放箱/搬箱完成时间来更新 cur
elif len(workR) == 0: cur = workL[0][0]
else: cur = min(workL[0][0], workR[0][0])
while workR:
t, i = heappop(workR) # 右边完成搬箱
# 如果没有排队，直接过桥；否则由于无论谁先过桥，最终完成时间都一样，所以也可以直接计算
cur = max(t, cur) + time[-i][2]
return cur # 最后一个过桥的时间