当前位置：首页 > news >正文

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

news 2026/5/22 3:29:49

下面给出 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 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]; // rightToLeft
heapPush(workLeft, [id, curTime + time[id][3]], true); // 到达左岸后放箱子
}
// 3. 否则，如果还有箱子要搬且左侧有人，派左侧工人过桥
else if (remain > 0 && waitLeft.length > 0) {
const [id] = heapPop(waitLeft, false)!;
curTime += time[id][0]; // leftToRight
heapPush(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;
}

使用示例：

// 示例 1
console.log(findCrossingTime(1, 3, [[1,1,2,1],[1,1,3,1],[1,1,4,1]])); // 输出: 6

// 示例 2
console.log(findCrossingTime(3, 2, [[1,9,1,8],[10,10,10,10]])); // 输出: 50

关键说明：

1. 效率排序：先按 leftToRight + rightToLeft 升序排序，总和越大效率越低；相同时下标大的效率低。排序后下标即可代表效率优先级。
2. 四个堆：
- waitLeft / waitRight：大顶堆，按效率值（下标）比较，效率最低的优先过桥。
- workLeft / workRight：小顶堆，按完成时间比较，时间到了移到等待队列。
3. 模拟逻辑：每次循环先处理完成工作的工人，然后优先让右侧工人过桥，其次才是左侧工人（且需有剩余箱子）。无人过桥时跳到下一个事件时间。
4. 收尾处理：所有箱子搬完后，右侧可能还有工人没回来，需要让他们依次过桥回到左岸。

时间复杂度 O((n+k) log k)，空间复杂度 O(k)，可高效通过题目数据范围。

查看全文

http://www.jsqmd.com/news/861920/