过桥的时间

题目

2532. 过桥的时间

---

共有 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 + rightToLeftj
• leftToRighti + rightToLefti == leftToRightj + rightToLeftj 且 i > j

工人通过桥时需要遵循以下规则：

• 如果工人 x 到达桥边时，工人 y 正在过桥，那么工人 x 需要在桥边等待。
• 如果没有正在过桥的工人，那么在桥右边等待的工人可以先过桥。如果同时有多个工人在右边等待，那么 效率最低 的工人会先过桥。
• 如果没有正在过桥的工人，且桥右边也没有在等待的工人，同时旧仓库还剩下至少一个箱子需要搬运，此时在桥左边的工人可以过桥。如果同时有多个工人在左边等待，那么 效率最低 的工人会先过桥。

所有 n 个盒子都需要放入新仓库，请你返回最后一个搬运箱子的工人 到达河左岸 的时间。

示例 1：

输入：n = 1, k = 3, time = [[1,1,2,1],[1,1,3,1],[1,1,4,1]]
输出：6
解释：
从 0 到 1 ：工人 2 从左岸过桥到达右岸。
从 1 到 2 ：工人 2 从旧仓库搬起一个箱子。
从 2 到 6 ：工人 2 从右岸过桥到达左岸。
从 6 到 7 ：工人 2 将箱子放入新仓库。
整个过程在 7 分钟后结束。因为问题关注的是最后一个工人到达左岸的时间，所以返回 6 。

示例 2：

输入：n = 3, k = 2, time = [[1,9,1,8],[10,10,10,10]]
输出：50
解释：
从 0 到 10 ：工人 1 从左岸过桥到达右岸。
从 10 到 20 ：工人 1 从旧仓库搬起一个箱子。
从 10 到 11 ：工人 0 从左岸过桥到达右岸。
从 11 到 20 ：工人 0 从旧仓库搬起一个箱子。
从 20 到 30 ：工人 1 从右岸过桥到达左岸。
从 30 到 40 ：工人 1 将箱子放入新仓库。
从 30 到 31 ：工人 0 从右岸过桥到达左岸。
从 31 到 39 ：工人 0 将箱子放入新仓库。
从 39 到 40 ：工人 0 从左岸过桥到达右岸。
从 40 到 49 ：工人 0 从旧仓库搬起一个箱子。
从 49 到 50 ：工人 0 从右岸过桥到达左岸。
从 50 到 58 ：工人 0 将箱子放入新仓库。
整个过程在 58 分钟后结束。因为问题关注的是最后一个工人到达左岸的时间，所以返回 50 。

提示：

• 1 <= n, k <= 10^4
• time.length == k
• time[i].length == 4
• 1 <= leftToRighti, pickOldi, rightToLefti, putNewi <= 1000

题解

方法一：

思路

比赛时大致思路正确用四个堆模拟即可，但是读题理解错误，以为桥左右两边同时有人等待要按照效率小的先行。
首先根据效率比较的条件将k个人按照效率由大到小排序，这时候下标大的效率越小。
用四个堆模拟:

1. 桥左侧等待过桥的大根堆l1，存储每个人的下标，由于同侧等待的人效率小的人先行动，故用大根堆。
2. 桥右侧等待过桥的大根堆r1，存储每个人的下标，由于同侧等待的人效率小的人先行动，故用大根堆。
3. 桥左侧放置箱子的小根堆l2，存储时间和人的下标。
4. 桥右侧放置箱子的小根堆r2，存储时间和人的下标。

对于当前桥空闲时间T，对于l2内小于桥空闲的当前时刻T的元素移动到l1中。对于r2内小于桥空闲的当前时刻T的元素移动到r1中。

若r1非空则选择r1堆顶元素过桥，更新下一次桥空闲时刻T，并将过桥且放置箱子的时间存入l2中；

若r1空但l1非空则选择l1堆顶元素过桥，更新下一次桥空闲时刻T，并将过桥且搬完箱子箱子的时间存入r2中，总共有n个箱子要搬，左侧最多只有n个人需要过桥，让n自减1；

若l1且r1都为空，就选择从l2和r2中最小的时间更新下一次桥空闲的时刻T。

最后当n为0时，只需继续运作右侧两个队列，计算出最后一个人过桥的时间便是答案。

代码

class Solution {
public:
    const int INF = 0x3f3f3f3f;
    int findCrossingTime(int n, int k, vector<vector<int>>& time) {
        //效率从大到小排序
        stable_sort(time.begin(), time.end(), [](auto& a, auto& b) {
            return a[0]+a[2] < b[0]+b[2];
        });
        int T = 0;
        //等待过桥优先队列 (id) 效率低优先，效率低则id大，大根堆
        priority_queue<int> l1, r1;
        //搬箱子队列 (time, id) 时间小于当前时间T则入等待过桥队列，时间小优先，小根堆
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> l2,r2;
        for (int i=0; i<k; i++) {
            l1.emplace(i);
        }
        while (n) {
            while (l2.size() && l2.top().first <= T) l1.emplace(l2.top().second), l2.pop();
            while (r2.size() && r2.top().first <= T) r1.emplace(r2.top().second), r2.pop();
            if (r1.size()) {
                auto x = r1.top(); r1.pop();
                T += time[x][2];
                l2.emplace(T+time[x][3], x);
            } else if (l1.size()) {
                auto x = l1.top(); l1.pop();
                T += time[x][0];
                r2.emplace(T+time[x][1], x);
                n--;
            } else {
                T = min((l2.size()?l2.top().first:INF), (r2.size()?r2.top().first:INF));
            }
        }
        //计算右边最后一个人回来的时间
        while (r1.size() || r2.size()) {
            while (r2.size() && r2.top().first <= T) r1.emplace(r2.top().second), r2.pop();
            if (r1.size()) {
                auto x = r1.top(); r1.pop();
                T += time[x][2];
            } else T = r2.top().first;
        }
        // while (r2.size()) {
        //     auto [x, y] = r2.top(); r2.pop();
        //     T = max(T, y)+time[x][2];
        // }
        return T;
    }
};