2532. 过桥的时间

Hard

题目描述

有 k 个工人想要把 n 个箱子从右边（旧）仓库搬到左边（新）仓库。给你两个整数 n 和 k，以及一个二维整数数组 time ，数组的大小是 k x 4 ，其中 time[i] = [righti, picki, lefti, puti] 。

仓库由一条河分隔，并通过一座桥连接。最初，所有 k 个工人都在桥的左侧等待。为了移动箱子，第 i 个工人可以：

花费 righti 分钟过桥到右侧。
花费 picki 分钟从右仓库拿一个箱子。
花费 lefti 分钟过桥到左侧。
花费 puti 分钟把箱子放到左仓库。

如果满足下面任一条件，那么第 i 个工人的效率比第 j 个工人低：

lefti + righti > leftj + rightj
lefti + righti == leftj + rightj 且 i > j

工人通过桥时，必须遵循以下规则：

一次只有一个工人可以使用桥。
桥空闲时，优先让已经拿到箱子的右侧效率最低的工人过桥。如果没有，则让左侧效率最低的工人过桥。
如果已经有足够的工人从左侧被派遣去拿剩余的所有箱子，就不会再从左侧派遣更多的工人。

返回最后一个箱子到达桥左侧的时刻。

示例 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,5,1,8],[10,10,10,10]]
输出：37
解释：
最后一个箱子在 37 秒时到达左侧。注意，我们不需要把最后的箱子放下，因为那会花费更多时间，而箱子已经和工人一起在左侧了。

提示：

1 <= n, k <= 10^4
time.length == k
time[i].length == 4
1 <= lefti, picki, righti, puti <= 1000

解题思路

这道题是一个复杂的模拟问题，需要使用优先队列来管理工人的调度。

问题分析：

需要跟踪每个工人的状态：在左侧等待、在桥上、在右侧工作、或在右侧等待返回
桥的使用规则：优先让已拿箱子的右侧最低效率工人过桥，否则让左侧最低效率工人过桥
工人效率定义：过桥总时间越长效率越低，时间相同时编号大的效率低

解题思路： 使用事件驱动的模拟方法：

维护四个优先队列：左侧等待过桥、左侧正在放箱子、右侧等待过桥、右侧正在拿箱子
按照工人效率排序（最低效率优先）
模拟整个过程，每次处理当前最早发生的事件
当有工人完成拿箱子或放箱子时，将其加入相应的等待队列
当桥空闲时，按规则选择下一个过桥的工人

算法步骤：

初始化所有工人在左侧等待
使用时间轴模拟，每次找到下一个事件时间
处理完成工作的工人，更新其状态
如果桥空闲且有工人等待，安排过桥
重复直到所有箱子都到达左侧

代码实现

class Solution {
public:
    int findCrossingTime(int n, int k, vector<vector<int>>& time) {
        // 根据效率排序的比较器
        auto cmp = [&](int a, int b) {
            int ta = time[a][0] + time[a][2];
            int tb = time[b][0] + time[b][2];
            if (ta != tb) return ta < tb;
            return a < b;
        };
        
        // 四个优先队列
        priority_queue<int, vector<int>, decltype(cmp)> leftWait(cmp);  // 左侧等待过桥
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> leftWork;  // 左侧工作（完成时间，工人编号）
        priority_queue<int, vector<int>, decltype(cmp)> rightWait(cmp); // 右侧等待过桥
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> rightWork; // 右侧工作（完成时间，工人编号）
        
        // 初始化所有工人在左侧
        for (int i = 0; i < k; i++) {
            leftWait.push(i);
        }
        
        int curTime = 0;
        int boxesMoved = 0;
        
        while (boxesMoved < n) {
            // 处理完成工作的工人
            while (!leftWork.empty() && leftWork.top().first <= curTime) {
                leftWait.push(leftWork.top().second);
                leftWork.pop();
            }
            while (!rightWork.empty() && rightWork.top().first <= curTime) {
                rightWait.push(rightWork.top().second);
                rightWork.pop();
            }
            
            // 安排过桥
            if (!rightWait.empty()) {
                // 右侧有工人等待过桥（已拿箱子）
                int worker = rightWait.top();
                rightWait.pop();
                curTime += time[worker][2];  // 过桥时间
                boxesMoved++;
                if (boxesMoved == n) {
                    return curTime;  // 最后一个箱子到达左侧
                }
                leftWork.push({curTime + time[worker][3], worker});  // 放箱子
            } else if (!leftWait.empty() && leftWait.size() + leftWork.size() > n - boxesMoved) {
                // 左侧有工人等待且还需要工人
                int worker = leftWait.top();
                leftWait.pop();
                curTime += time[worker][0];  // 过桥时间
                rightWork.push({curTime + time[worker][1], worker});  // 拿箱子
            } else {
                // 桥空闲，推进时间到下一个事件
                int nextTime = INT_MAX;
                if (!leftWork.empty()) {
                    nextTime = min(nextTime, leftWork.top().first);
                }
                if (!rightWork.empty()) {
                    nextTime = min(nextTime, rightWork.top().first);
                }
                curTime = nextTime;
            }
        }
        
        return curTime;
    }
};

class Solution:
    def findCrossingTime(self, n: int, k: int, time: List[List[int]]) -> int:
        import heapq
        
        # 根据效率排序（最低效率优先）
        def efficiency(i):
            return time[i][0] + time[i][2]
        
        # 四个优先队列
        left_wait = [(-efficiency(i), -i) for i in range(k)]  # 左侧等待过桥
        heapq.heapify(left_wait)
        left_work = []  # 左侧工作（完成时间，工人编号）
        right_wait = []  # 右侧等待过桥
        right_work = []  # 右侧工作（完成时间，工人编号）
        
        cur_time = 0
        boxes_moved = 0
        
        while boxes_moved < n:
            # 处理完成工作的工人
            while left_work and left_work[0][0] <= cur_time:
                _, worker = heapq.heappop(left_work)
                heapq.heappush(left_wait, (-efficiency(worker), -worker))
                
            while right_work and right_work[0][0] <= cur_time:
                _, worker = heapq.heappop(right_work)
                heapq.heappush(right_wait, (-efficiency(worker), -worker))
            
            # 安排过桥
            if right_wait:
                # 右侧有工人等待过桥（已拿箱子）
                _, neg_worker = heapq.heappop(right_wait)
                worker = -neg_worker
                cur_time += time[worker][2]  # 过桥时间
                boxes_moved += 1
                if boxes_moved == n:
                    return cur_time  # 最后一个箱子到达左侧
                heapq.heappush(left_work, (cur_time + time[worker][3], worker))  # 放箱子
            elif left_wait and len(left_wait) + len(left_work) > n - boxes_moved:
                # 左侧有工人等待且还需要工人
                _, neg_worker = heapq.heappop(left_wait)
                worker = -neg_worker
                cur_time += time[worker][0]  # 过桥时间
                heapq.heappush(right_work, (cur_time + time[worker][1], worker))  # 拿箱子
            else:
                # 桥空闲，推进时间到下一个事件
                next_time = float('inf')
                if left_work:
                    next_time = min(next_time, left_work[0][0])
                if right_work:
                    next_time = min(next_time, right_work[0][0])
                cur_time = next_time
        
        return cur_time

public class Solution {
    public int FindCrossingTime(int n, int k, int[][] time) {
        // 根据效率排序的比较器
        var leftWait = new SortedSet<(int eff, int id)>();  // 左侧等待过桥
        var leftWork = new SortedSet<(int time, int id)>();  // 左侧工作
        var rightWait = new SortedSet<(int eff, int id)>();  // 右侧等待过桥
        var rightWork = new SortedSet<(int time, int id)>();  // 右侧工作
        
        // 初始化所有工人在左侧
        for (int i = 0; i < k; i++) {
            int eff = time[i][0] + time[i][2];
            leftWait.Add((eff, i));
        }
        
        int curTime = 0;
        int boxesMoved = 0;
        
        while (boxesMoved < n) {
            // 处理完成工作的工人
            var toRemoveLeft = new List<(int, int)>();
            foreach (var (t, id) in leftWork) {
                if (t <= curTime) {
                    toRemoveLeft.Add((t, id));
                    int eff = time[id][0] + time[id][2];
                    leftWait.Add((eff, id));
                } else break;
            }
            foreach (var item in toRemoveLeft) {
                leftWork.Remove(item);
            }
            
            var toRemoveRight = new List<(int, int)>();
            foreach (var (t, id) in rightWork) {
                if (t <= curTime) {
                    toRemoveRight.Add((t, id));
                    int eff = time[id][0] + time[id][2];
                    rightWait.Add((eff, id));
                } else break;
            }
            foreach (var item in toRemoveRight) {
                rightWork.Remove(item);
            }
            
            // 安排过桥
            if (rightWait.Count > 0) {
                var (eff, worker) = rightWait.Max;
                rightWait.Remove((eff, worker));
                curTime += time[worker][2];  // 过桥时间
                boxesMoved++;
                if (boxesMoved == n) {
                    return curTime;  // 最后一个箱子到达左侧
                }
                leftWork.Add((curTime + time[worker][3], worker));  // 放箱子
            } else if (leftWait.Count > 0 && leftWait.Count + leftWork.Count > n - boxesMoved) {
                var (eff, worker) = leftWait.Max;
                leftWait.Remove((eff, worker));
                curTime += time[worker][0];  // 过桥时间
                rightWork.Add((curTime + time[worker][1], worker));  // 拿箱子
            } else {
                // 桥空闲，推进时间到下一个事件
                int nextTime = int.MaxValue;
                if (leftWork.Count > 0) {
                    nextTime = Math.Min(nextTime, leftWork.Min.time);
                }
                if (rightWork.Count > 0) {
                    nextTime = Math.Min(nextTime, rightWork.Min.time);
                }
                curTime = nextTime;
            }
        }
        
        return curTime;
    }
}

var findCrossingTime = function(n, k, time) {
    const efficiency = (i) => time[i][0] + time[i][2];
    
    // Priority queues using arrays and manual sorting
    let leftWaiting = [];
    let rightWaiting = [];
    let leftWorking = [];
    let rightWorking = [];
    
    // Initialize all workers on left side
    for (let i = 0; i < k; i++) {
        leftWaiting.push(i);
    }
    
    // Sort by efficiency (less efficient first, higher index for ties)
    const sortByEfficiency = (arr) => {
        arr.sort((a, b) => {
            const effA = efficiency(a);
            const effB = efficiency(b);
            if (effA !== effB) return effB - effA;
            return b - a;
        });
    };
    
    sortByEfficiency(leftWaiting);
    
    let currentTime = 0;
    let boxesMoved = 0;
    let workersDispatchedRight = 0;
    
    while (boxesMoved < n) {
        // Move workers from working to waiting if their tasks are done
        leftWorking = leftWorking.filter(worker => {
            if (worker.finishTime <= currentTime) {
                leftWaiting.push(worker.id);
                return false;
            }
            return true;
        });
        
        rightWorking = rightWorking.filter(worker => {
            if (worker.finishTime <= currentTime) {
                rightWaiting.push(worker.id);
                return false;
            }
            return true;
        });
        
        sortByEfficiency(leftWaiting);
        sortByEfficiency(rightWaiting);
        
        // Check if we have workers ready to cross
        let canCrossFromRight = rightWaiting.length > 0;
        let canCrossFromLeft = leftWaiting.length > 0 && workersDispatchedRight < n;
        
        if (canCrossFromRight) {
            // Worker crosses from right to left
            let worker = rightWaiting.pop();
            currentTime += time[worker][2]; // left crossing time
            boxesMoved++;
            
            // Worker puts box (starts working on left)
            leftWorking.push({
                id: worker,
                finishTime: currentTime + time[worker][3]
            });
        } else if (canCrossFromLeft) {
            // Worker crosses from left to right
            let worker = leftWaiting.pop();
            currentTime += time[worker][0]; // right crossing time
            workersDispatchedRight++;
            
            // Worker picks box (starts working on right)
            rightWorking.push({
                id: worker,
                finishTime: currentTime + time[worker][1]
            });
        } else {
            // No one can cross, advance time to next available worker
            let nextTime = Infinity;
            
            for (let worker of leftWorking) {
                nextTime = Math.min(nextTime, worker.finishTime);
            }
            for (let worker of rightWorking) {
                nextTime = Math.min(nextTime, worker.finishTime);
            }
            
            currentTime = nextTime;
        }
    }
    
    return currentTime;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	复杂度	说明
时间复杂度	O(n × k × log k)	每个箱子需要两次过桥，每次操作涉及优先队列的插入删除，最坏情况下需要O(k log k)时间
空间复杂度	O(k)	需要存储k个工人的状态信息

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目