LeetCode 2532: Time to Cross a Bridge Solution

Master LeetCode problem 2532 (Time to Cross a Bridge), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2532. Time to Cross a Bridge

Hard

Array Heap (Priority Queue)Simulation

Problem Explanation

Explanation:

To solve this problem, we can simulate the movement of workers across the bridge. We will maintain two priority queues, one for the workers on the left side of the bridge and one for the workers on the right side. We will iterate through time steps, moving workers according to the given rules.

Create a class Worker to represent each worker with their index, time to cross to the right, pick up time, time to cross back, and put down time.
Create two priority queues, pqRight and pqLeft, to keep track of workers on the right and left sides of the bridge.
Initialize a variable timeElapsed to keep track of the current time.
Iterate through time steps, moving workers across the bridge based on the rules provided.
Keep track of the number of boxes picked up and the number of workers who have crossed back to the left side.
Return the elapsed time when the last box reaches the left side.

Time Complexity: O(nlogn), where n is the number of workers. Space Complexity: O(n).

Solution Code

import java.util.*;

class Worker {
    int index, rightTime, pickTime, leftTime, putTime;

    public Worker(int index, int rightTime, int pickTime, int leftTime, int putTime) {
        this.index = index;
        this.rightTime = rightTime;
        this.pickTime = pickTime;
        this.leftTime = leftTime;
        this.putTime = putTime;
    }
}

public int timeToCrossBridge(int n, int k, int[][] time) {
    PriorityQueue<Worker> pqRight = new PriorityQueue<>((a, b) -> a.rightTime - b.rightTime);
    PriorityQueue<Worker> pqLeft = new PriorityQueue<>((a, b) -> a.leftTime - b.leftTime);
    
    for (int i = 0; i < k; i++) {
        Worker worker = new Worker(i, time[i][0], time[i][1], time[i][2], time[i][3]);
        pqRight.offer(worker);
    }
    
    int timeElapsed = 0, boxesPicked = 0, workersBack = 0;
    
    while (boxesPicked < n) {
        if (!pqRight.isEmpty() && (pqLeft.isEmpty() || pqRight.peek().rightTime <= timeElapsed)) {
            Worker worker = pqRight.poll();
            timeElapsed = Math.max(timeElapsed, worker.rightTime);
            timeElapsed += worker.pickTime;
            pqLeft.offer(worker);
            boxesPicked++;
        } else {
            Worker worker = pqLeft.poll();
            timeElapsed = Math.max(timeElapsed, worker.leftTime);
            timeElapsed += worker.putTime;
            workersBack++;
            if (workersBack >= k) break;
        }
    }
    
    return timeElapsed;
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2532 (Time to Cross a Bridge)?

This page provides optimized solutions for LeetCode problem 2532 (Time to Cross a Bridge) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2532 (Time to Cross a Bridge)?

The time complexity for LeetCode 2532 (Time to Cross a Bridge) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2532 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2532 in Java, C++, or Python.

Back to LeetCode Solutions