同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
共有 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 + rightToLeftj
leftToRighti + 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 <= 104
time.length == k
time[i].length == 4
1 <= leftToRighti, pickOldi, rightToLefti, putNewi <= 1000
我们先将工人按照效率从高到底排序,这样,下标越大的工人,效率越低。
接下来,我们用四个优先队列模拟工人的状态:
wait_in_left
:大根堆,存储当前在左岸等待的工人的下标;wait_in_right
:大根堆,存储当前在右岸等待的工人的下标;work_in_left
:小根堆,存储当前在左岸工作的工人放好箱子的时间以及工人的下标;work_in_right
:小根堆,存储当前在右岸工作的工人拿好箱子的时间以及工人的下标。初始时,所有工人都在左岸,因此 wait_in_left
中存储所有工人的下标。用变量 cur
记录当前时间。
然后,我们模拟整个过程。我们先判断当前时刻,work_in_left
是否有工人已经放好箱子,如果有,我们将工人放入 wait_in_left
中,然后将工人从 work_in_left
中移除。同理,我们再判断 work_in_right
是否有工人已经放好箱子,如果有,我们将工人放入 wait_in_right
中,然后将工人从 work_in_right
中移除。
接着,我们判断当前时刻是否有工人在左岸等待,记为 left_to_go
,同时,我们判断当前时刻是否有工人在右岸等待,记为 right_to_go
。如果不存在等待过岸的工人,我们直接将 cur
更新为下一个工人放好箱子的时间,然后继续模拟过程。
如果 right_to_go
为 true
,我们从 wait_in_right
中取出一个工人,更新 cur
为当前时间加上该工人从右岸过左岸的时间,如果此时所有工人都已经过了右岸,我们直接将 cur
作为答案返回;否则,我们将该工人放入 work_in_left
中。
如果 left_to_go
为 true
,我们从 wait_in_left
中取出一个工人,更新 cur
为当前时间加上该工人从左岸过右岸的时间,然后将该工人放入 work_in_right
中,并且将箱子数量减一。
循环上述过程,直到箱子数量为零,此时 cur
即为答案。
时间复杂度 $O(n \times \log k)$,空间复杂度 $O(k)$。其中 $n$ 和 $k$ 分别为工人数量和箱子数量。
class Solution:
def findCrossingTime(self, n: int, k: int, time: List[List[int]]) -> int:
time.sort(key=lambda x: x[0] + x[2])
cur = 0
wait_in_left, wait_in_right = [], []
work_in_left, work_in_right = [], []
for i in range(k):
heappush(wait_in_left, -i)
while 1:
while work_in_left:
t, i = work_in_left[0]
if t > cur:
break
heappop(work_in_left)
heappush(wait_in_left, -i)
while work_in_right:
t, i = work_in_right[0]
if t > cur:
break
heappop(work_in_right)
heappush(wait_in_right, -i)
left_to_go = n > 0 and wait_in_left
right_to_go = bool(wait_in_right)
if not left_to_go and not right_to_go:
nxt = inf
if work_in_left:
nxt = min(nxt, work_in_left[0][0])
if work_in_right:
nxt = min(nxt, work_in_right[0][0])
cur = nxt
continue
if right_to_go:
i = -heappop(wait_in_right)
cur += time[i][2]
if n == 0 and not wait_in_right and not work_in_right:
return cur
heappush(work_in_left, (cur + time[i][3], i))
else:
i = -heappop(wait_in_left)
cur += time[i][0]
n -= 1
heappush(work_in_right, (cur + time[i][1], i))
class Solution {
public int findCrossingTime(int n, int k, int[][] time) {
int[][] t = new int[k][5];
for (int i = 0; i < k; ++i) {
int[] x = time[i];
t[i] = new int[] {x[0], x[1], x[2], x[3], i};
}
Arrays.sort(t, (a, b) -> {
int x = a[0] + a[2], y = b[0] + b[2];
return x == y ? a[4] - b[4] : x - y;
});
int cur = 0;
PriorityQueue<Integer> waitInLeft = new PriorityQueue<>((a, b) -> b - a);
PriorityQueue<Integer> waitInRight = new PriorityQueue<>((a, b) -> b - a);
PriorityQueue<int[]> workInLeft = new PriorityQueue<>((a, b) -> a[0] - b[0]);
PriorityQueue<int[]> workInRight = new PriorityQueue<>((a, b) -> a[0] - b[0]);
for (int i = 0; i < k; ++i) {
waitInLeft.offer(i);
}
while (true) {
while (!workInLeft.isEmpty()) {
int[] p = workInLeft.peek();
if (p[0] > cur) {
break;
}
waitInLeft.offer(workInLeft.poll()[1]);
}
while (!workInRight.isEmpty()) {
int[] p = workInRight.peek();
if (p[0] > cur) {
break;
}
waitInRight.offer(workInRight.poll()[1]);
}
boolean leftToGo = n > 0 && !waitInLeft.isEmpty();
boolean rightToGo = !waitInRight.isEmpty();
if (!leftToGo && !rightToGo) {
int nxt = 1 << 30;
if (!workInLeft.isEmpty()) {
nxt = Math.min(nxt, workInLeft.peek()[0]);
}
if (!workInRight.isEmpty()) {
nxt = Math.min(nxt, workInRight.peek()[0]);
}
cur = nxt;
continue;
}
if (rightToGo) {
int i = waitInRight.poll();
cur += t[i][2];
if (n == 0 && waitInRight.isEmpty() && workInRight.isEmpty()) {
return cur;
}
workInLeft.offer(new int[] {cur + t[i][3], i});
} else {
int i = waitInLeft.poll();
cur += t[i][0];
--n;
workInRight.offer(new int[] {cur + t[i][1], i});
}
}
}
}
class Solution {
public:
int findCrossingTime(int n, int k, vector<vector<int>>& time) {
using pii = pair<int, int>;
for (int i = 0; i < k; ++i) {
time[i].push_back(i);
}
sort(time.begin(), time.end(), [](auto& a, auto& b) {
int x = a[0] + a[2], y = b[0] + b[2];
return x == y ? a[4] < b[4] : x < y;
});
int cur = 0;
priority_queue<int> waitInLeft, waitInRight;
priority_queue<pii, vector<pii>, greater<pii>> workInLeft, workInRight;
for (int i = 0; i < k; ++i) {
waitInLeft.push(i);
}
while (true) {
while (!workInLeft.empty()) {
auto [t, i] = workInLeft.top();
if (t > cur) {
break;
}
workInLeft.pop();
waitInLeft.push(i);
}
while (!workInRight.empty()) {
auto [t, i] = workInRight.top();
if (t > cur) {
break;
}
workInRight.pop();
waitInRight.push(i);
}
bool leftToGo = n > 0 && !waitInLeft.empty();
bool rightToGo = !waitInRight.empty();
if (!leftToGo && !rightToGo) {
int nxt = 1 << 30;
if (!workInLeft.empty()) {
nxt = min(nxt, workInLeft.top().first);
}
if (!workInRight.empty()) {
nxt = min(nxt, workInRight.top().first);
}
cur = nxt;
continue;
}
if (rightToGo) {
int i = waitInRight.top();
waitInRight.pop();
cur += time[i][2];
if (n == 0 && waitInRight.empty() && workInRight.empty()) {
return cur;
}
workInLeft.push({cur + time[i][3], i});
} else {
int i = waitInLeft.top();
waitInLeft.pop();
cur += time[i][0];
--n;
workInRight.push({cur + time[i][1], i});
}
}
}
};
func findCrossingTime(n int, k int, time [][]int) int {
sort.SliceStable(time, func(i, j int) bool { return time[i][0]+time[i][2] < time[j][0]+time[j][2] })
waitInLeft := hp{}
waitInRight := hp{}
workInLeft := hp2{}
workInRight := hp2{}
for i := range time {
heap.Push(&waitInLeft, i)
}
cur := 0
for {
for len(workInLeft) > 0 {
if workInLeft[0].t > cur {
break
}
heap.Push(&waitInLeft, heap.Pop(&workInLeft).(pair).i)
}
for len(workInRight) > 0 {
if workInRight[0].t > cur {
break
}
heap.Push(&waitInRight, heap.Pop(&workInRight).(pair).i)
}
leftToGo := n > 0 && waitInLeft.Len() > 0
rightToGo := waitInRight.Len() > 0
if !leftToGo && !rightToGo {
nxt := 1 << 30
if len(workInLeft) > 0 {
nxt = min(nxt, workInLeft[0].t)
}
if len(workInRight) > 0 {
nxt = min(nxt, workInRight[0].t)
}
cur = nxt
continue
}
if rightToGo {
i := heap.Pop(&waitInRight).(int)
cur += time[i][2]
if n == 0 && waitInRight.Len() == 0 && len(workInRight) == 0 {
return cur
}
heap.Push(&workInLeft, pair{cur + time[i][3], i})
} else {
i := heap.Pop(&waitInLeft).(int)
cur += time[i][0]
n--
heap.Push(&workInRight, pair{cur + time[i][1], i})
}
}
}
type hp struct{ sort.IntSlice }
func (h hp) Less(i, j int) bool { return h.IntSlice[i] > h.IntSlice[j] }
func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any {
a := h.IntSlice
v := a[len(a)-1]
h.IntSlice = a[:len(a)-1]
return v
}
type pair struct{ t, i int }
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 any) { *h = append(*h, v.(pair)) }
func (h *hp2) Pop() any { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。