What is the main strategy to solve the Time to Cross a Bridge problem?

The main strategy involves simulating the movement of workers using an array for task tracking and a heap to optimize task scheduling.

How does using a heap help with the solution?

A heap efficiently manages the scheduling of workers, ensuring the next available worker is selected with minimal delay and optimizing the process.

What is the time complexity of this problem?

The time complexity is O(k log k), where `k` is the number of workers, due to heap insertions and deletions during the simulation.

What are some common mistakes to avoid when solving this problem?

Common mistakes include not simulating worker tasks correctly, using inefficient data structures, or overcomplicating the problem when a simple simulation with heaps suffices.

Can the problem be extended or made more complex?

Yes, the problem can be extended by adding more complex worker efficiencies, multiple tasks, or different crossing speeds, requiring advanced simulation techniques.

#2532

Hard

auto_awesome堆

LeetCode 题解工作台

过桥的时间

共有 k 位工人计划将 n 个箱子从右侧的（旧）仓库移动到左侧的（新）仓库。给你两个整数 n 和 k ，以及一个二维整数数组 time ，数组的大小为 k x 4 ，其中 time[i] = [right i , pick i , left i , put i ] 。一条河将两座仓库分隔，只能通过…

数组堆（优先队列）模拟

题目描述

共有 k 位工人计划将 n 个箱子从右侧的（旧）仓库移动到左侧的（新）仓库。给你两个整数 n 和 k，以及一个二维整数数组 time ，数组的大小为 k x 4 ，其中 time[i] = [right_i, pick_i, left_i, put_i] 。

一条河将两座仓库分隔，只能通过一座桥通行。旧仓库位于河的右岸，新仓库在河的左岸。开始时，所有 k 位工人都在桥的左侧等待。为了移动这些箱子，第 i 位工人（下标从 0 开始）可以：

从左岸（新仓库）跨过桥到右岸（旧仓库），用时 right_i 分钟。
从旧仓库选择一个箱子，并返回到桥边，用时 pick_i 分钟。不同工人可以同时搬起所选的箱子。
从右岸（旧仓库）跨过桥到左岸（新仓库），用时 left_i 分钟。
将箱子放入新仓库，并返回到桥边，用时 put_i 分钟。不同工人可以同时放下所选的箱子。

如果满足下面任一条件，则认为工人 i 的 效率低于 工人 j ：

left_i + right_i > left_j + right_j
left_i + right_i == left_j + right_j 且 i > j

工人通过桥时需要遵循以下规则：

同时只能有一名工人过桥。
当桥梁未被使用时，优先让右侧 效率最低 的工人（已经拿起盒子的工人）过桥。如果不是，优先让左侧 效率最低 的工人通过。
如果左侧已经派出足够的工人来拾取所有剩余的箱子，则不会再从左侧派出工人。

请你返回最后一个箱子 到达桥左侧 的时间。

示例 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,5,1,8],[10,10,10,10]]

输出：37

解释：

最后一个盒子在37秒时到达左侧。请注意，我们并没有放下最后一个箱子，因为那样会花费更多时间，而且它们已经和工人们一起在左边。

提示：

1 <= n, k <= 10⁴
time.length == k
time[i].length == 4
1 <= left_i, pick_i, right_i, put_i <= 1000

lightbulb

解题思路

方法一：优先队列（大小根堆） + 模拟

我们先将工人按照效率从高到底排序，这样，下标越大的工人，效率越低。

接下来，我们用四个优先队列模拟工人的状态：

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$ 分别为工人数量和箱子数量。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

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))

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Test the candidate's ability to simulate processes efficiently.
question_mark
Evaluate how well the candidate optimizes worker task management using heaps.
question_mark
Gauge the candidate's understanding of time complexity in relation to heap operations.

warning

常见陷阱

外企场景

error
Failing to properly simulate each worker's task time, leading to incorrect timing calculations.
error
Not utilizing the heap structure correctly to optimize the worker scheduling process.
error
Overcomplicating the solution instead of using a simple simulation with an efficient heap management.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Adding constraints where some workers might have different efficiencies, requiring more advanced scheduling logic.
arrow_right_alt
Allowing workers to perform additional tasks, such as multiple box pick-ups or drops, complicating the simulation process.
arrow_right_alt
Adjusting the time for various tasks, like allowing for different crossing speeds for each worker.

help

常见问题

外企场景

继续练习

#2558 从数量最多的堆取走礼物 #2500 删除每行中的最大值 #2593 标记所有元素后数组的分数