过桥的时间【LC2532】
共有 k 位工人计划将 n 个箱子从旧仓库移动到新仓库。给你两个整数 n 和 k，以及一个二维整数数组 time ，数组的大小为 k x 4 ，其中 time[i] = [leftToRighti, pickOldi, rightToLefti, putNewi] 。
一条河将两座仓库分隔，只能通过一座桥通行。旧仓库位于河的右岸，新仓库在河的左岸。开始时，所有 k 位工人都在桥的左侧等待。为了移动这些箱子，第 i 位工人（下标从 0 开始）可以：
- 从左岸（新仓库）跨过桥到右岸（旧仓库），用时
leftToRighti分钟。 - 从旧仓库选择一个箱子，并返回到桥边，用时
pickOldi分钟。不同工人可以同时搬起所选的箱子。 - 从右岸（旧仓库）跨过桥到左岸（新仓库），用时
rightToLefti分钟。 - 将箱子放入新仓库，并返回到桥边，用时
putNewi分钟。不同工人可以同时放下所选的箱子。
如果满足下面任一条件，则认为工人 i 的 效率低于 工人 j ：
leftToRighti + rightToLefti > leftToRightj + rightToLeftjleftToRighti + rightToLefti == leftToRightj + rightToLeftj且i > j
工人通过桥时需要遵循以下规则：
- 如果工人
x到达桥边时，工人y正在过桥，那么工人x需要在桥边等待。 - 如果没有正在过桥的工人，那么在桥右边等待的工人可以先过桥。如果同时有多个工人在右边等待，那么 效率最低 的工人会先过桥
- 如果没有正在过桥的工人，且桥右边也没有在等待的工人，同时旧仓库还剩下至少一个箱子需要搬运，此时在桥左边的工人可以过桥。如果同时有多个工人在左边等待，那么 效率最低 的工人会先过桥。
所有 n 个盒子都需要放入新仓库，请你返回最后一个搬运箱子的工人 到达河左岸 的时间。
思路：使用四个堆存放工人的下标和完成事件或者到达桥的时间，然后根据要求过桥、搬运箱子，放回最后一个搬运箱子的工人到达河左岸的时间
- 首先将
time数组排序，排序后下标越大，效率越低，优先级越高 - 使用四个堆存放工人的下标和完成事件或者到达桥的时间
workL：新仓库正在放箱的工人【在当前时间之前的所有工人均以完成事件，因此根据时间从小到大排序】
waitL：新仓库等待过桥的工人【低效率的先过桥，根据下标从大到小排序】【到达对岸的时间非必须，辅助作用】
workR：旧仓库正在拿箱的工人【在当前时间之前的所有工人均以完成事件，因此根据时间从小到大排序】
waitLR：旧仓库等待过桥的工人【低效率的先过桥，根据下标从大到小排序】
- 使用变量
cur记录当前的时间，初始时，所有工人位于新仓库，因此将所有节点放入waitL - 然后模拟整个流程，计算n个工人从旧仓库到达新仓库，并选择箱子的时间
将workL和workR中所有完成工作的工人，放入排队列表
选择右岸效率最低的工人过桥，若无，再选择左岸效率最低的工人过桥：时间cur移动至其到达对岸的时间节点，并更新其完成工作的时间，最后将其放入工作列表
若两个排队列表均为空，说明工人都在working，那么选择最快完成工作的工人，让他排队过桥
最后，计算所有工人回到左岸的时间，返回最终时间即可
分析可知，此时waitR一定没有元素【因为退出循环的条件是有n个员工到达右岸，如果waitR中有元素的话，n一定不为0，因此最后一个员工到达右岸时，waitR一定没有元素】，而workR一定有元素，其他两个堆是否有元素不影响结果，因此将workR中工作的所有员工依次出队，若当前时间在其完成工作的时间之前，那么需要更新当前时间为其完成工作的时间，然后将当前时间更新为其到达左岸的时间，最后返回cur【堆中根据完成时间从小到大排序，而每次只能过桥一个员工，因此可得最终时间】
实现
复杂度
时间复杂度：O ( n + l o g k )
空间复杂度：O ( k )
