Leetcode 2532(硬)。是时候过桥了。
#编程 #算法 #ios #swift

描述

k工人想要将n盒子从旧仓库移至新仓库。为您提供了两个整数nk,以及一个尺寸k x 4的2D整数Array time

仓库被河流分开,并由桥梁连接。旧仓库位于河的右岸,新仓库位于河的左岸。最初,所有k工人都在桥的左侧等待。要移动盒子,i-thenter( 0-索引)可以:

  • leftToRighti分钟内从左岸(新仓库)到右岸(旧仓库)的桥梁。
  • 从旧仓库中挑选一个盒子,然后返回pickOldi分钟的桥。不同的工人可以同时拿起盒子。
  • rightToLefti分钟内从右岸(旧仓库)越过桥(旧仓库)。
  • 将盒子放在新仓库中,然后在putNewi分钟内返回桥。不同的工人可以同时放他们的盒子。

如果满足两种条件,则i的效率低于工人j

  • leftToRighti + rightToLefti > leftToRightj + rightToLeftj
  • leftToRighti + rightToLefti == leftToRightj + rightToLeftji > 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

LeetCode TOP 200 Sergey Leschev

方法

代码中的主要循环处理以下步骤:

  1. 更新桥梁上的等待列表。
  2. 选择一个工人根据定义的条件通过桥梁。
  3. 推进时间。
  4. 更新需要移动的剩余框的计数。

值得注意的点:

  1. 当右岸有足够的工人时,左侧的工人不应经过桥梁。
  2. 当没有工人在等着两边的桥梁时,时间就移至下一时刻,工人可能会等待越过。

LeetCode TOP 200 Sergey Leschev

代码(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

LeetCode TOP 200 Sergey Leschev


联系人
我明确专注于上市时间,而没有优先考虑技术债务。我作为系统建筑师,移动(ios-swift,android-kotlin),前端(react-typescript)和后端(nodejs-.net-.net-php-php-php-php-kafka-sql)参加了系统架构师的预售/RFX活动。 -nosql)。我还通过知识转移到成功交付的知识转移,成立了预售作为CTO的工作。

在 ð§电子邮件: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
ð网站:https://sergeyleschev.github.io
ðreddit:https://reddit.com/user/sergeyleschev
ðQuora:https://quora.com/sergey-leschev
ð媒介:https://medium.com/@sergeyleschev
□pdf设计模式:Download