描述
有k
工人想要将n
盒子从旧仓库移至新仓库。为您提供了两个整数n
和k
,以及一个尺寸k x 4
的2D整数Array time
。
仓库被河流分开,并由桥梁连接。旧仓库位于河的右岸,新仓库位于河的左岸。最初,所有k
工人都在桥的左侧等待。要移动盒子,i
-thenter( 0-索引)可以:
- 在
leftToRighti
分钟内从左岸(新仓库)到右岸(旧仓库)的桥梁。 - 从旧仓库中挑选一个盒子,然后返回
pickOldi
分钟的桥。不同的工人可以同时拿起盒子。 - 在
rightToLefti
分钟内从右岸(旧仓库)越过桥(旧仓库)。 - 将盒子放在新仓库中,然后在
putNewi
分钟内返回桥。不同的工人可以同时放他们的盒子。
如果满足两种条件,则i
的效率低于工人j
:
leftToRighti + rightToLefti > leftToRightj + rightToLeftj
-
leftToRighti + rightToLefti == leftToRightj + rightToLeftj
和i > j
以下规则规范工人通过桥梁的运动:
- 如果一个工人
x
到达桥,而另一名工人y
越过桥,x
在桥的一侧等待。 - 如果桥是免费的,那么在桥的右侧等待的工人将越过桥梁。如果一个以上的工人在右侧等待,那么最低效率的一名首先要交叉。
- 如果桥是免费的,没有工人在右侧等待,并且至少有一个盒子留在旧仓库中,则河左侧的工人可以越过桥。如果一个以上的工人在左侧等待,那么效率最低的一个人首先交叉。
返回 在将所有n个盒子放在新仓库中后,最后一名工人到达河的左岸的时间。<<<<<<<<<<<< /em>
示例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.
示例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.
约束:
1 <= n,k <= 10^4
time.length == k
时间[i] .length == 4
1 <= lefttorighti,pickoldi,righttolefti,putnewi <= 1000
方法
代码中的主要循环处理以下步骤:
- 更新桥梁上的等待列表。
- 选择一个工人根据定义的条件通过桥梁。
- 推进时间。
- 更新需要移动的剩余框的计数。
值得注意的点:
- 当右岸有足够的工人时,左侧的工人不应经过桥梁。
- 当没有工人在等着两边的桥梁时,时间就移至下一时刻,工人可能会等待越过。
代码(Swift)
已经考虑了溢出检查。移动盒子的最大时间最多是4 * 1000(四个步骤移动盒子,每个步骤需要1000时间)。最多使用1e4盒,总时间最多为4E7,确保解决方案是安全的。
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
}
}
}
来源:Github
联系人
我明确专注于上市时间,而没有优先考虑技术债务。我作为系统建筑师,移动(ios-swift,android-kotlin),前端(react-typescript)和后端(nodejs-.net-.net-php-php-php-php-kafka-sql)参加了系统架构师的预售/RFX活动。 -nosql)。我还通过知识转移到成功交付的知识转移,成立了预售作为CTO的工作。
ðLinkedIn:https://linkedin.com/in/sergeyleschev/
ðleetcode:https://leetcode.com/sergeyleschev/
ðTwitter:https://twitter.com/sergeyleschev
ðgithub:https://github.com/sergeyleschev
ð网站:https://sergeyleschev.github.io
ðreddit:https://reddit.com/user/sergeyleschev
ðQuora:https://quora.com/sergey-leschev
ð媒介:https://medium.com/@sergeyleschev
□pdf设计模式:Download