千问 LeetCode 2532.过桥的时间 TypeScript实现

下面给出 TypeScript 实现思路与 Java 版本一致使用四个优先队列模拟function findCrossingTime(n: number, k: number, time: number[][]): number {// 1. 按效率排序leftToRight rightToLeft 越大效率越低相同时下标越大效率越低// 排序后下标即可代表效率优先级time.sort((a, b) (a[0] a[2]) - (b[0] b[2]));// 等待过桥的工人大顶堆效率最低的优先// 存储 [效率值, 下标]const waitLeft: number[][] [];const waitRight: number[][] [];// 正在工作的工人小顶堆按完成时间排序// 存储 [下标, 完成时间]const workLeft: number[][] [];const workRight: number[][] [];// 堆操作辅助函数const heapPush (heap: number[][], item: number[], isMinHeap: boolean) {heap.push(item);let i heap.length - 1;while (i 0) {const parent Math.floor((i - 1) / 2);const compare isMinHeap? heap[i][1] heap[parent][1]: heap[i][0] heap[parent][0];if (compare) {[heap[i], heap[parent]] [heap[parent], heap[i]];i parent;} else break;}};const heapPop (heap: number[][], isMinHeap: boolean): number[] | undefined {if (heap.length 0) return undefined;const top heap[0];const last heap.pop()!;if (heap.length 0) {heap[0] last;let i 0;const n heap.length;while (true) {let smallest i;const left 2 * i 1;const right 2 * i 2;if (left n) {const compare isMinHeap? heap[left][1] heap[smallest][1]: heap[left][0] heap[smallest][0];if (compare) smallest left;}if (right n) {const compare isMinHeap? heap[right][1] heap[smallest][1]: heap[right][0] heap[smallest][0];if (compare) smallest right;}if (smallest ! i) {[heap[i], heap[smallest]] [heap[smallest], heap[i]];i smallest;} else break;}}return top;};const heapPeek (heap: number[][]): number[] | undefined heap[0];// 初始所有工人在左侧等待for (let i k - 1; i 0; i--) {heapPush(waitLeft, [i, 0], false); // 大顶堆按效率值下标比较}let curTime 0;let remain n; // 剩余需要搬运的箱子数while (remain 0 || workRight.length 0 || waitRight.length 0) {// 1. 将当前时间前完成工作的工人移到等待队列while (workLeft.length 0 heapPeek(workLeft)![1] curTime) {const [id] heapPop(workLeft, true)!;heapPush(waitLeft, [id, 0], false);}while (workRight.length 0 heapPeek(workRight)![1] curTime) {const [id] heapPop(workRight, true)!;heapPush(waitRight, [id, 0], false);}// 2. 优先让右侧工人过桥if (waitRight.length 0) {const [id] heapPop(waitRight, false)!;curTime time[id][2]; // rightToLeftheapPush(workLeft, [id, curTime time[id][3]], true); // 到达左岸后放箱子}// 3. 否则如果还有箱子要搬且左侧有人派左侧工人过桥else if (remain 0 waitLeft.length 0) {const [id] heapPop(waitLeft, false)!;curTime time[id][0]; // leftToRightheapPush(workRight, [id, curTime time[id][1]], true); // 到达右岸后搬箱子remain--;}// 4. 无人过桥时间跳到下一个事件发生的时间else {let nextTime Infinity;if (workLeft.length 0) nextTime Math.min(nextTime, heapPeek(workLeft)![1]);if (workRight.length 0) nextTime Math.min(nextTime, heapPeek(workRight)![1]);curTime nextTime;}}// 收尾所有箱子已搬完让右侧所有工人依次过桥回到左岸while (workRight.length 0) {const [id, finishTime] heapPop(workRight, true)!;curTime Math.max(curTime, finishTime) time[id][2];}while (waitRight.length 0) {const [id] heapPop(waitRight, false)!;curTime time[id][2];}return curTime;}使用示例// 示例 1console.log(findCrossingTime(1, 3, [[1,1,2,1],[1,1,3,1],[1,1,4,1]])); // 输出: 6// 示例 2console.log(findCrossingTime(3, 2, [[1,9,1,8],[10,10,10,10]])); // 输出: 50关键说明1. 效率排序先按 leftToRight rightToLeft 升序排序总和越大效率越低相同时下标大的效率低。排序后下标即可代表效率优先级。2. 四个堆- waitLeft / waitRight大顶堆按效率值下标比较效率最低的优先过桥。- workLeft / workRight小顶堆按完成时间比较时间到了移到等待队列。3. 模拟逻辑每次循环先处理完成工作的工人然后优先让右侧工人过桥其次才是左侧工人且需有剩余箱子。无人过桥时跳到下一个事件时间。4. 收尾处理所有箱子搬完后右侧可能还有工人没回来需要让他们依次过桥回到左岸。时间复杂度 O((nk) log k)空间复杂度 O(k)可高效通过题目数据范围。