Skip to content

2532. Time to Cross a Bridge

Description

There are k workers who want to move n boxes from the right (old) warehouse to the left (new) warehouse. You are given the two integers n and k, and a 2D integer array time of size k x 4 where time[i] = [righti, picki, lefti, puti].

The warehouses are separated by a river and connected by a bridge. Initially, all k workers are waiting on the left side of the bridge. To move the boxes, the ith worker can do the following:

  • Cross the bridge to the right side in righti minutes.
  • Pick a box from the right warehouse in picki minutes.
  • Cross the bridge to the left side in lefti minutes.
  • Put the box into the left warehouse in puti minutes.

The ith worker is less efficient than the jth worker if either condition is met:

  • lefti + righti > leftj + rightj
  • lefti + righti == leftj + rightj and i > j

The following rules regulate the movement of the workers through the bridge:

  • Only one worker can use the bridge at a time.
  • When the bridge is unused prioritize the least efficient worker on the right side to cross. If there are no workers on the right side, prioritize the least efficient worker on the left side to cross.
  • If enough workers have already been dispatched from the left side to pick up all the remaining boxes, no more workers will be sent from the left side.

Return the elapsed minutes at which the last box reaches the left side of the bridge.

 

Example 1:

Input: n = 1, k = 3, time = [[1,1,2,1],[1,1,3,1],[1,1,4,1]]

Output: 6

Explanation:

From 0 to 1 minutes: worker 2 crosses the bridge to the right.
From 1 to 2 minutes: worker 2 picks up a box from the right warehouse.
From 2 to 6 minutes: worker 2 crosses the bridge to the left.
From 6 to 7 minutes: worker 2 puts a box at the left warehouse.
The whole process ends after 7 minutes. We return 6 because the problem asks for the instance of time at which the last worker reaches the left side of the bridge.

Example 2:

Input: n = 3, k = 2, time = [[1,9,1,8],[10,10,10,10]]

Output: 50

Explanation:

From 0  to 10: worker 1 crosses the bridge to the right.
From 10 to 20: worker 1 picks up a box from the right warehouse.
From 10 to 11: worker 0 crosses the bridge to the right.
From 11 to 20: worker 0 picks up a box from the right warehouse.
From 20 to 30: worker 1 crosses the bridge to the left.
From 30 to 40: worker 1 puts a box at the left warehouse.
From 30 to 31: worker 0 crosses the bridge to the left.
From 31 to 39: worker 0 puts a box at the left warehouse.
From 39 to 40: worker 0 crosses the bridge to the right.
From 40 to 49: worker 0 picks up a box from the right warehouse.
From 49 to 50: worker 0 crosses the bridge to the left.

 

Constraints:

  • 1 <= n, k <= 104
  • time.length == k
  • time[i].length == 4
  • 1 <= leftToRighti, pickOldi, rightToLefti, putNewi <= 1000

Solutions

Solution 1: Priority Queue (Max-Heap and Min-Heap) + Simulation

First, we sort the workers by efficiency in descending order, so the worker with the highest index has the lowest efficiency.

Next, we use four priority queues to simulate the state of the workers:

  • wait_in_left: Max-heap, storing the indices of workers currently waiting on the left bank;
  • wait_in_right: Max-heap, storing the indices of workers currently waiting on the right bank;
  • work_in_left: Min-heap, storing the time when workers currently working on the left bank finish placing boxes and the indices of the workers;
  • work_in_right: Min-heap, storing the time when workers currently working on the right bank finish picking up boxes and the indices of the workers.

Initially, all workers are on the left bank, so wait_in_left stores the indices of all workers. We use the variable cur to record the current time.

Then, we simulate the entire process. First, we check if any worker in work_in_left has finished placing boxes at the current time. If so, we move the worker to wait_in_left and remove the worker from work_in_left. Similarly, we check if any worker in work_in_right has finished picking up boxes. If so, we move the worker to wait_in_right and remove the worker from work_in_right.

Next, we check if there are any workers waiting on the left bank at the current time, denoted as left_to_go. At the same time, we check if there are any workers waiting on the right bank, denoted as right_to_go. If there are no workers waiting to cross the river, we directly update cur to the next time when a worker finishes placing boxes and continue the simulation.

If right_to_go is true, we take a worker from wait_in_right, update cur to the current time plus the time it takes for the worker to cross from the right bank to the left bank. If all workers have crossed to the right bank at this point, we directly return cur as the answer; otherwise, we move the worker to work_in_left.

If left_to_go is true, we take a worker from wait_in_left, update cur to the current time plus the time it takes for the worker to cross from the left bank to the right bank, then move the worker to work_in_right and decrement the number of boxes.

Repeat the above process until the number of boxes is zero. At this point, cur is the answer.

The time complexity is $O(n \times \log k)$, and the space complexity is $O(k)$. Here, $n$ and $k$ are the number of workers and the number of boxes, respectively.

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

 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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
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});
            }
        }
    }
}

 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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
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});
            }
        }
    }
};

 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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
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 }

Comments