Skip to content

2532. Time to Cross a Bridge 👎

  • Time: $O(n\log n)$
  • Space: $O(n)$
 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
class Solution {
 public:
  int findCrossingTime(int n, int k, vector<vector<int>>& time) {
    int ans = 0;
    using P = pair<int, int>;
    // (leftToRight + rightToLeft, i)
    priority_queue<P> leftBridgeQueue;
    priority_queue<P> rightBridgeQueue;
    // (time to be idle, i)
    priority_queue<P, vector<P>, greater<>> leftWorkers;
    priority_queue<P, vector<P>, greater<>> rightWorkers;

    for (int i = 0; i < k; ++i)
      leftBridgeQueue.emplace(
          /*leftToRight*/ time[i][0] + /*rightToLeft*/ time[i][2], i);

    while (n > 0 || !rightBridgeQueue.empty() || !rightWorkers.empty()) {
      // Idle left workers get on the left bridge.
      while (!leftWorkers.empty() && leftWorkers.top().first <= ans) {
        const int i = leftWorkers.top().second;
        leftWorkers.pop();
        leftBridgeQueue.emplace(
            /*leftToRight*/ time[i][0] + /*rightToLeft*/ time[i][2], i);
      }
      // Idle right workers get on the right bridge.
      while (!rightWorkers.empty() && rightWorkers.top().first <= ans) {
        const int i = rightWorkers.top().second;
        rightWorkers.pop();
        rightBridgeQueue.emplace(
            /*leftToRight*/ time[i][0] + /*rightToLeft*/ time[i][2], i);
      }

      if (!rightBridgeQueue.empty()) {
        // If the bridge is free, the worker waiting on the right side of the
        // bridge gets to cross the bridge. If more than one worker is waiting
        // on the right side, the one with the lowest efficiency crosses first.
        const int i = rightBridgeQueue.top().second;
        rightBridgeQueue.pop();
        ans += /*rightToLeft*/ time[i][2];
        leftWorkers.emplace(ans + /*putNew*/ time[i][3], i);
      } else if (!leftBridgeQueue.empty() && n > 0) {
        // If the bridge is free and no worker is waiting on the right side, and
        // at least one box remains at the old warehouse, the worker on the left
        // side of the river gets to cross the bridge. If more than one worker
        // is waiting on the left side, the one with the lowest efficiency
        // crosses first.
        const int i = leftBridgeQueue.top().second;
        leftBridgeQueue.pop();
        ans += /*leftToRight*/ time[i][0];
        rightWorkers.emplace(ans + /*pickOld*/ time[i][1], i);
        --n;
      } else {
        // Advance the time of the last crossing worker.
        ans = min(
            !leftWorkers.empty() && n > 0 ? leftWorkers.top().first : INT_MAX,
            !rightWorkers.empty() ? rightWorkers.top().first : INT_MAX);
      }
    }

    return ans;
  }
};

 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
class Solution {
  public int findCrossingTime(int n, int k, int[][] time) {
    int ans = 0;
    // (leftToRight + rightToLeft, i)
    Queue<Pair<Integer, Integer>> leftBridgeQueue = createMaxHeap();
    Queue<Pair<Integer, Integer>> rightBridgeQueue = createMaxHeap();
    // (time to be idle, i)
    Queue<Pair<Integer, Integer>> leftWorkers = createMinHeap();
    Queue<Pair<Integer, Integer>> rightWorkers = createMinHeap();

    for (int i = 0; i < k; ++i)
      leftBridgeQueue.offer(new Pair<>(
          /*leftToRight*/ time[i][0] + /*rightToLeft*/ time[i][2], i));

    while (n > 0 || !rightBridgeQueue.isEmpty() || !rightWorkers.isEmpty()) {
      // Idle left workers get on the left bridge.
      while (!leftWorkers.isEmpty() && leftWorkers.peek().getKey() <= ans) {
        final int i = leftWorkers.poll().getValue();
        leftBridgeQueue.offer(new Pair<>(
            /*leftToRight*/ time[i][0] + /*rightToLeft*/ time[i][2], i));
      }
      // Idle right workers get on the right bridge.
      while (!rightWorkers.isEmpty() && rightWorkers.peek().getKey() <= ans) {
        final int i = rightWorkers.poll().getValue();
        rightBridgeQueue.offer(new Pair<>(
            /*leftToRight*/ time[i][0] + /*rightToLeft*/ time[i][2], i));
      }

      if (!rightBridgeQueue.isEmpty()) {
        // If the bridge is free, the worker waiting on the right side of the
        // bridge gets to cross the bridge. If more than one worker is waiting
        // on the right side, the one with the lowest efficiency crosses first.
        final int i = rightBridgeQueue.poll().getValue();
        ans += /*rightToLeft*/ time[i][2];
        leftWorkers.offer(new Pair<>(ans + /*putNew*/ time[i][3], i));
      } else if (!leftBridgeQueue.isEmpty() && n > 0) {
        // If the bridge is free and no worker is waiting on the right side, and
        // at least one box remains at the old warehouse, the worker on the left
        // side of the river gets to cross the bridge. If more than one worker
        // is waiting on the left side, the one with the lowest efficiency
        // crosses first.
        final int i = leftBridgeQueue.poll().getValue();
        ans += /*leftToRight*/ time[i][0];
        rightWorkers.offer(new Pair<>(ans + /*pickOld*/ time[i][1], i));
        --n;
      } else {
        // Advance the time of the last crossing worker.
        ans = Math.min(!leftWorkers.isEmpty() && n > 0 ? leftWorkers.peek().getKey()
                                                       : Integer.MAX_VALUE,
                       !rightWorkers.isEmpty() ? rightWorkers.peek().getKey() : Integer.MAX_VALUE);
      }
    }

    return ans;
  }

  private Queue<Pair<Integer, Integer>> createMaxHeap() {
    return new PriorityQueue<>((a, b)
                                   -> a.getKey().equals(b.getKey()) ? b.getValue() - a.getValue()
                                                                    : b.getKey() - a.getKey());
  }

  private Queue<Pair<Integer, Integer>> createMinHeap() {
    return new PriorityQueue<>((a, b)
                                   -> a.getKey().equals(b.getKey()) ? a.getValue() - b.getValue()
                                                                    : a.getKey() - b.getKey());
  }
}

 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
class Solution:
  def findCrossingTime(self, n: int, k: int, time: List[List[int]]) -> int:
    ans = 0
    # (leftToRight + rightToLeft, i)
    leftBridgeQueue = [(-leftToRight - rightToLeft, -i)
                       for i, (leftToRight, pickOld, rightToLeft, pickNew) in enumerate(time)]
    rightBridgeQueue = []
    # (time to be idle, i)
    leftWorkers = []
    rightWorkers = []

    heapq.heapify(leftBridgeQueue)

    while n > 0 or rightBridgeQueue or rightWorkers:
      # Idle left workers get on the left bridge.
      while leftWorkers and leftWorkers[0][0] <= ans:
        i = heapq.heappop(leftWorkers)[1]
        leftWorkers.pop()
        heapq.heappush(leftBridgeQueue, (-time[i][0] - time[i][2], -i))
      # Idle right workers get on the right bridge.
      while rightWorkers and rightWorkers[0][0] <= ans:
        i = heapq.heappop(rightWorkers)[1]
        heapq.heappush(rightBridgeQueue, (-time[i][0] - time[i][2], -i))
      if rightBridgeQueue:
        # If the bridge is free, the worker waiting on the right side of the
        # bridge gets to cross the bridge. If more than one worker is waiting
        # on the right side, the one with the lowest efficiency crosses first.
        i = -heapq.heappop(rightBridgeQueue)[1]
        ans += time[i][2]
        heapq.heappush(leftWorkers, (ans + time[i][3], i))
      elif leftBridgeQueue and n > 0:
        # If the bridge is free and no worker is waiting on the right side, and
       # at least one box remains at the old warehouse, the worker on the left
       # side of the river gets to cross the bridge. If more than one worker
       # is waiting on the left side, the one with the lowest efficiency
       # crosses first.
        i = -heapq.heappop(leftBridgeQueue)[1]
        ans += time[i][0]
        heapq.heappush(rightWorkers, (ans + time[i][1], i))
        n -= 1
      else:
        # Advance the time of the last crossing worker.
        ans = min(leftWorkers[0][0] if leftWorkers and n > 0 else math.inf,
                  rightWorkers[0][0] if rightWorkers else math.inf)

    return ans