Leetcode 2532. Time to Cross a Bridge

[Woodyiiiiiii]

这是周赛第四题——模拟题。好像第一次见这种类型的hard难度，所以记录下。

这类题型是用堆进行模拟。抓住变量：时间、优先级和独立过程(过桥)。

过程如下：

1. 排序
2. 桥左右两边分别用两个堆进行模拟，一个代表正在等待，一个代表正在装/卸货
3. 用while(true)进行模拟过程：首先判断当前时间是否有工人完成装/卸货，然后加入等待队列；接着判断左右两边过桥，同时更新堆
4. 终止条件是n等于0且桥右边没有任何工人在等待或者装货

class Solution {
    public int findCrossingTime(int n, int k, int[][] time) {
        // sort time by less efficiency
        int[][] timeCopy = new int[k][5];
        for (int i = 0; i < k; i++) {
            System.arraycopy(time[i], 0, timeCopy[i], 0, 4);
            timeCopy[i][4] = i;
        }
        Arrays.sort(timeCopy, (o1, o2) -> {
            if (o1[0] + o1[2] == o2[0] + o2[2]) {
                return o2[4] - o1[4];
            }
            return o2[0] + o2[2] - o1[0] - o1[2];
        });

        // left and right waiting pq sorted by low efficiency
        PriorityQueue<Integer> pqWaitingLeft = new PriorityQueue<>();
        PriorityQueue<Integer> pqWaitingRight = new PriorityQueue<>();
        // left and right putting pq sorted by time
        PriorityQueue<Pair> pqPuttingLeft = new PriorityQueue<>((o1, o2) -> {
            if (o1.arriveTime == o2.arriveTime) {
                return o1.i - o2.i;
            }
            return o1.arriveTime - o2.arriveTime;
        });
        PriorityQueue<Pair> pqPuttingRight = new PriorityQueue<>((o1, o2) -> {
            if (o1.arriveTime == o2.arriveTime) {
                return o1.i - o2.i;
            }
            return o1.arriveTime - o2.arriveTime;
        });

        // init
        for (int i = 0; i < k; i++) {
            pqWaitingLeft.add(i);
        }

        // simulate
        int timeNow = 0;
        while (true) {
            // check if someone finishes putting
            while (!pqPuttingLeft.isEmpty()) {
                if (pqPuttingLeft.peek().arriveTime <= timeNow) {
                    pqWaitingLeft.add(pqPuttingLeft.poll().i);
                } else {
                    break;
                }
            }
            while (!pqPuttingRight.isEmpty()) {
                if (pqPuttingRight.peek().arriveTime <= timeNow) {
                    pqWaitingRight.add(pqPuttingRight.poll().i);
                } else {
                    break;
                }
            }

            // simulate crossing
            boolean leftGo = n > 0 && !pqWaitingLeft.isEmpty();
            boolean rightGo = !pqWaitingRight.isEmpty();
            if (!leftGo && !rightGo) {
                int minTime = Integer.MAX_VALUE;
                if (!pqPuttingLeft.isEmpty()) {
                    minTime = Math.min(minTime, pqPuttingLeft.peek().arriveTime);
                }
                if (!pqPuttingRight.isEmpty()) {
                    minTime = Math.min(minTime, pqPuttingRight.peek().arriveTime);
                }
                timeNow = minTime;
            } else if (rightGo) {
                int i = pqWaitingRight.poll();
                timeNow += timeCopy[i][2];

                // no boxes and no workers on right side
                if (n == 0 && pqWaitingRight.isEmpty() && pqPuttingRight.isEmpty()) {
                    return timeNow;
                }
                pqPuttingLeft.add(new Pair(timeNow + timeCopy[i][3], i));
            } else {
                int i = pqWaitingLeft.poll();
                timeNow += timeCopy[i][0];
                pqPuttingRight.add(new Pair(timeNow + timeCopy[i][1], i));
                n--;
            }
        }
    }

    static class Pair {
        int arriveTime;
        int i;
        public Pair(int arriveTime, int i) {
            this.arriveTime = arriveTime;
            this.i = i;
        }
    }
}

类似模拟题：

• 1834. Single-Threaded CPU
• 2462. Total Cost to Hire K Workers
• 2402. Meeting Rooms III

---

• https://leetcode.com/problems/time-to-cross-a-bridge/description/
• https://leetcode.cn/problems/time-to-cross-a-bridge/solutions/2050850/by-tsreaper-clsg/