Description
There are k
workers who want to move n
boxes from an old warehouse to a new one. You are given the two integers n
and k
, and a 2D integer array time
of size k x 4
where time[i] = [leftToRighti, pickOldi, rightToLefti, putNewi]
.
The warehouses are separated by a river and connected by a bridge. The old warehouse is on the right bank of the river, and the new warehouse is on the left bank of the river. Initially, all k
workers are waiting on the left side of the bridge. To move the boxes, the i
th worker (0indexed) can :
 Cross the bridge from the left bank (new warehouse) to the right bank (old warehouse) in
leftToRighti
minutes.  Pick a box from the old warehouse and return to the bridge in
pickOldi
minutes. Different workers can pick up their boxes simultaneously.  Cross the bridge from the right bank (old warehouse) to the left bank (new warehouse) in
rightToLefti
minutes.  Put the box in the new warehouse and return to the bridge in
putNewi
minutes. Different workers can put their boxes simultaneously.
A worker i
is less efficient than a worker j
if either condition is met:
leftToRighti + rightToLefti > leftToRightj + rightToLeftj

leftToRighti + rightToLefti == leftToRightj + rightToLeftj
andi > j
The following rules regulate the movement of the workers through the bridge:
 If a worker
x
reaches the bridge while another workery
is crossing the bridge,x
waits at their side of the bridge.  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.
 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.
Return the instance of time at which the last worker reaches the left bank of the river after all n boxes have been put in the new warehouse.
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: worker 2 crosses the bridge from the left bank to the right bank.
From 1 to 2: worker 2 picks up a box from the old warehouse.
From 2 to 6: worker 2 crosses the bridge from the right bank to the left bank.
From 6 to 7: worker 2 puts a box at the new 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 bank.
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 from the left bank to the right bank.
From 10 to 20: worker 1 picks up a box from the old warehouse.
From 10 to 11: worker 0 crosses the bridge from the left bank to the right bank.
From 11 to 20: worker 0 picks up a box from the old warehouse.
From 20 to 30: worker 1 crosses the bridge from the right bank to the left bank.
From 30 to 40: worker 1 puts a box at the new warehouse.
From 30 to 31: worker 0 crosses the bridge from the right bank to the left bank.
From 31 to 39: worker 0 puts a box at the new warehouse.
From 39 to 40: worker 0 crosses the bridge from the left bank to the right bank.
From 40 to 49: worker 0 picks up a box from the old warehouse.
From 49 to 50: worker 0 crosses the bridge from the right bank to the left bank.
From 50 to 58: worker 0 puts a box at the new warehouse.
The whole process ends after 58 minutes. We return 50 because the problem asks for the instance of time at which the last worker reaches the left bank.
Constraints:
1 <= n, k <= 10^4
time.length == k
time[i].length == 4
1 <= leftToRighti, pickOldi, rightToLefti, putNewi <= 1000
Approach
The main forloop in the code handles the following steps:
 Update the waiting list on the bridge.
 Pick a worker to pass the bridge based on the defined conditions.
 Advance the time.
 Update the count of remaining boxes that need to be moved.
Noteworthy points:
 When there are enough workers on the right bank, workers on the left side should not pass the bridge.
 When there are no workers waiting to cross the bridge on either side, the time is moved to the next moment when a worker could potentially be waiting to cross.
Code (Swift)
Overflow checks have been taken into consideration. The maximum time to move a box is at most 4 * 1000 (four steps to move the box, each taking 1000 time). With at most 1e4 boxes, the total time is at most 4e7, ensuring the solution is safe.
class Solution {
func findCrossingTime(_ n: Int, _ k: Int, _ time: [[Int]]) > Int {
var lBank = PriorityQueue<Int>(comparator: { (a, b) > Bool in
let ta = time[a]
let tb = time[b]
let ca = ta[0] + ta[2]
let cb = tb[0] + tb[2]
if ca == cb { return b < a } // larger index cross first
return cb < ca // larger cross time cross first
})
var rBank = PriorityQueue<Int>(comparator: { (a, b) > Bool in
let ta = time[a]
let tb = time[b]
let ca = ta[0] + ta[2]
let cb = tb[0] + tb[2]
if ca == cb { return b < a } // larger index cross first
return cb < ca // larger cross time cross first
})
// 0 > time of the worker will be waiting to cross the bridge, 1 >idx
var lWorker = PriorityQueue<(Int, Int)>(comparator: { (a, b) > Bool in a.0 < b.0 })
var rWorker = PriorityQueue<(Int, Int)>(comparator: { (a, b) > Bool in a.0 < b.0 })
// initially, all at left bank
for i in 0..<k {
lBank.add(i)
}
var curTime = 0
var remainingBoxes = n
while remainingBoxes > 0 {
// process worker
while !lWorker.isEmpty && lWorker.peek()!.0 <= curTime {
lBank.add(lWorker.poll()!.1)
}
while !rWorker.isEmpty && rWorker.peek()!.0 <= curTime {
rBank.add(rWorker.poll()!.1)
}
var worker = 1
if !rBank.isEmpty {
// right side can pass, a box will be put
worker = rBank.poll()!
let t = time[worker]
lWorker.add((curTime + t[2] + t[3], worker))
curTime += t[2] // right to left
remainingBoxes = 1
} else if !lBank.isEmpty && (remainingBoxes > rBank.size + rWorker.size) {
// left side can pass
// left side only pass when there are more boxes
worker = lBank.poll()!
let t = time[worker]
rWorker.add((curTime + t[0] + t[1], worker))
curTime += t[0] // left to right
} else if remainingBoxes == rBank.size + rWorker.size {
curTime = rWorker.peek()!.0
} else {
// if still empty, advance time
let nxt: Int
if rWorker.isEmpty {
nxt = lWorker.peek()!.0
} else if lWorker.isEmpty {
nxt = rWorker.peek()!.0
} else {
nxt = min(lWorker.peek()!.0, rWorker.peek()!.0)
}
curTime = nxt
}
}
return curTime
}
}
// Wrapper class for PriorityQueue
struct PriorityQueue<Element> {
private var heap: [Element]
private let comparator: (Element, Element) > Bool
init(comparator: @escaping (Element, Element) > Bool) {
self.heap = []
self.comparator = comparator
}
var isEmpty: Bool {
return heap.isEmpty
}
var size: Int {
return heap.count
}
func peek() > Element? {
return heap.first
}
mutating func add(_ element: Element) {
heap.append(element)
swim(heap.count  1)
}
mutating func poll() > Element? {
if heap.isEmpty { return nil }
if heap.count == 1 { return heap.removeFirst() }
heap.swapAt(0, heap.count  1)
let element = heap.removeLast()
sink(0)
return element
}
private mutating func swim(_ index: Int) {
var childIndex = index
var parentIndex = (childIndex  1) / 2
while childIndex > 0 && comparator(heap[childIndex], heap[parentIndex]) {
heap.swapAt(childIndex, parentIndex)
childIndex = parentIndex
parentIndex = (childIndex  1) / 2
}
}
private mutating func sink(_ index: Int) {
var parentIndex = index
while true {
let leftChildIndex = 2 * parentIndex + 1
let rightChildIndex = 2 * parentIndex + 2
var candidateIndex = parentIndex
if leftChildIndex < heap.count && comparator(heap[leftChildIndex], heap[candidateIndex])
{
candidateIndex = leftChildIndex
}
if rightChildIndex < heap.count
&& comparator(heap[rightChildIndex], heap[candidateIndex])
{
candidateIndex = rightChildIndex
}
if candidateIndex == parentIndex {
return
}
heap.swapAt(parentIndex, candidateIndex)
parentIndex = candidateIndex
}
}
}
Sources: Github
Contacts
I have a clear focus on timetomarket and don't prioritize technical debt. And I took part in the PreSale/RFX activity as a System Architect, assessment efforts for Mobile (iOSSwift, AndroidKotlin), Frontend (ReactTypeScript) and Backend (NodeJS.NETPHPKafkaSQLNoSQL). And I also formed the work of PreSale as a CTO from Opportunity to Proposal via knowledge transfer to Successful Delivery.
🛩️ #startups #management #cto #swift #typescript #database
📧 Email: sergey.leschev@gmail.com
👋 LinkedIn: https://linkedin.com/in/sergeyleschev/
👋 LeetCode: https://leetcode.com/sergeyleschev/
👋 Twitter: https://twitter.com/sergeyleschev
👋 Github: https://github.com/sergeyleschev
🌎 Website: https://sergeyleschev.github.io
🌎 Reddit: https://reddit.com/user/sergeyleschev
🌎 Quora: https://quora.com/sergeyleschev
🌎 Medium: https://medium.com/@sergeyleschev
🖨️ PDF Design Patterns: Download
Top comments (4)
I do not understand. is that narrative with a moral ending in it ? or are we supposed to solve something ? That is a long story man.
I can see you got badges man. plenty of badges. You a pro or something?
The code simulates box movement using priority heaps for efficient processing. It selects workers based on defined conditions, advances time, and updates box count. The solution handles corner cases and ensures safe execution. Overall, it efficiently computes the required time for box movement.
Could you please let me know what specific part of the explanation you'd like me to elaborate on? I'll be more than happy to provide additional details to make it crystal clear for you! 🌟🤗
kwaaaaaaaaaaaaaaaaaaaaaaaahhhhh lol :you a funny guy ....I love you man... ......you jus made my day !!!!
dude you are like the Mike Tyson of coding. I am waaaay behind.I got a long way to go... Every time I read the first paragraph i pass out.
Some comments have been hidden by the post's author  find out more