2532. 过桥的时间 - Kotlin 复杂模拟+优先队列

原题地址：https://leetcode.cn/problems/time-to-cross-a-bridge/description/

题解

定义一个工人由以下几个部分组成：

• index：工人序号
• LtR：从左桥过桥的时间
• up：从右仓库拿起箱子并返回右桥的时间
• RtL：从右桥过桥的时间
• down：从左仓库放下箱子并返回左桥的时间
• time：工人进入仓库的时间（当在桥边等待时无意义）

可以得知

• 当工人进入左仓库操作时，操作完毕的时刻是timer+down
• 当工人进入右仓库操作时，操作完毕的时刻是timer+up

我们维护一个timer计时器记录当前的时刻点

优先队列：

• 对于桥边排队的优先队列，我们每次都取效率最低的，根据题意很容易写出桥边队列的Comparator，即效率逆序排序
• 对于仓库中的优先队列，我们考虑每次timer更新时，必定是timer+up/down即完成时刻较小的人从仓库中被移出并加入桥边队列，即完成时刻升序排序

当工人过桥时，不论仓库中的工人如何进展，操作完毕后都只能在桥边队列等待，因此在过桥后我们可以直接在timer加上工人过桥的时间

过桥分为四个步骤，以从右桥过桥为例

• 过桥工人=右桥队列中效率最低的工人
• timer计时器+=过桥工人过桥的耗时
• 过桥工人进入左仓库
• 过桥工人的time属性记为当前timer

根据题意定义的优先级：

• 当右桥队列有人时，令效率最低的人过桥
  • 当右桥队列此时为空，且右仓库的箱子数量为空时，则说明当前工人已为最后一个工人，返回过桥后timer
• 当左桥队列有人且右仓库中工人数量小于右仓库中箱子数量时，令效率最低的人过桥
• 当两边队列均无人（可能所有工人都在仓库中操作），timer++空闲等待

class Solution {
    fun findCrossingTime(n: Int, k: Int, time: Array<IntArray>): Int {
        /*
            工人数组定义
            |0      |1      |2      |3      |4      |5
            |index  |LtR    |up     |RtL    |down   |time（进入仓库的时间，完成作业时间即timer+up/down）
         */
        val efficiency = Comparator<IntArray> { a, b ->
            if (a[1] + a[3] != b[1] + b[3]) {
                (b[1] + b[3]) - (a[1] + a[3])
            } else {
                b[0] - a[0]
            }
        }
        val pickUp = Comparator<IntArray> { a, b -> (a[5] + a[2]) - (b[5] + b[2]) }
        val pickDown = Comparator<IntArray> { a, b -> (a[5] + a[4]) - (b[5] + b[4]) }

        val leftWorkers = PriorityQueue(efficiency)     //左桥排队
        val rightWorkers = PriorityQueue(efficiency)    //右桥排队
        val leftRepo = PriorityQueue(pickDown)          //左仓库操作中工人
        val rightRepo = PriorityQueue(pickUp)           //右仓库操作中工人

        var leftCnt = 0     //左仓库箱子数量
        var rightCnt = n    //右仓库箱子数量
        var timer = 0       //计时器

        var worker: IntArray
        for ((index, arr) in time.withIndex()) {
            leftWorkers.add(intArrayOf(index) + arr + intArrayOf(0))
        }

        while (leftCnt < n) {
            //由于计时器更新，刷新仓库中工人状态，操作完毕的工人回到桥上等待
            while (leftRepo.size > 0 && leftRepo.first()[5] + leftRepo.first()[4] <= timer) {
                leftWorkers.add(leftRepo.remove())
                leftCnt++
            }
            while (rightRepo.size > 0 && rightRepo.first()[5] + rightRepo.first()[2] <= timer) {
                rightWorkers.add(rightRepo.remove())
                rightCnt--
            }
            if (rightWorkers.size > 0) {
                //右桥工人过桥，并进入左仓库
                worker = rightWorkers.remove()
                timer += worker[3]
                worker[5] = timer
                leftRepo.add(worker)

                //当前工人已为最后一个工人
                if (rightWorkers.size == 0 && rightCnt == 0) {
                    return timer
                }
            }else if(leftWorkers.size > 0 && rightRepo.size < rightCnt) {
                //左桥工人过桥，并进入右仓库
                worker = leftWorkers.remove()
                timer += worker[1]
                worker[5] = timer
                rightRepo.add(worker)
            }else {
                //空闲等待，桥边无人等待
                timer++
            }
        }
        return 0
    }
}