2332. 赶上公交车的最晚时间

Medium

题目描述

给你一个下标从 0 开始长度为 n 的整数数组 buses ，其中 buses[i] 表示第 i 辆公交车的出发时间。同时给你一个下标从 0 开始长度为 m 的整数数组 passengers ，其中 passengers[j] 表示第 j 位乘客的到达时间。所有公交车出发时间互不相同，所有乘客到达时间也互不相同。

给你一个整数 capacity ，表示每辆公交车最多能容纳的乘客数目。

当一位乘客到达时，他会排队等候下一辆公交车。你可以搭乘在第 x 分钟出发的公交车，前提是你在第 y 分钟到达，其中 y <= x 且公交车没有满载。按照到达时间最早的乘客优先上车。

更正式的，当一辆公交车到达时：

如果候车的乘客人数小于等于 capacity ，他们都会上车。
否则，会让 capacity 个 最早到达 的乘客上车。

返回你可以搭乘公交车的 最晚到达时间 。你不能跟别的乘客同时刻到达。

**注意：**数组 buses 和 passengers 不一定是有序的。

示例 1：

输入：buses = [10,20], passengers = [2,17,18,19], capacity = 2
输出：16
解释：假设你在时刻 16 到达。
时刻 10 时，第一辆公交车载着第 0 位乘客出发。
时刻 20 时，第二辆公交车载着你和第 1 位乘客出发。
注意你不能跟其他乘客同一时间到达，所以你必须在第 1 位乘客之前到达来赶上公交车。

示例 2：

输入：buses = [20,30,10], passengers = [19,13,26,4,25,11,21], capacity = 2
输出：20
解释：假设你在时刻 20 到达。
时刻 10 时，第一辆公交车载着第 3 位乘客出发。
时刻 20 时，第二辆公交车载着第 5 和第 1 位乘客出发。
时刻 30 时，第三辆公交车载着第 0 位乘客和你出发。
如果你更晚到达，那么第 6 位乘客会占据你在第三辆公交车上的位置。

提示：

n == buses.length
m == passengers.length
1 <= n, m, capacity <= 10^5
2 <= buses[i], passengers[i] <= 10^9
buses 中每个元素 互不相同
passengers 中每个元素 互不相同

解题思路

这道题的核心思路是模拟公交车载客过程，找到我们能搭乘的最晚时间。

解题思路：

排序预处理：首先对公交车时间和乘客到达时间进行排序，便于按时间顺序模拟。
模拟载客过程：使用双指针遍历每辆公交车，模拟乘客上车的过程：
- 对每辆公交车，统计有多少乘客可以上车（到达时间不超过发车时间且不超过容量）
- 记录每辆车实际载客情况
寻找最优策略：我们有两种上车策略：
- 抢占最后一个位置：如果最后一辆有空位的公交车未满载，我们可以在发车时间到达
- 挤掉其他乘客：在某辆公交车满载的情况下，我们可以比最后一个上车的乘客早1分钟到达，从而挤掉他
避免时间冲突：我们不能与其他乘客同时到达，所以如果选择的时间与某个乘客冲突，需要继续往前调整。

算法步骤：

模拟所有公交车的载客过程
从最后一辆车开始，尝试找到最晚的可行到达时间
检查时间冲突并调整

这种方法时间复杂度为 O(n log n + m log m)，主要消耗在排序上。

代码实现

class Solution {
public:
    int latestTimeCatchTheBus(vector<int>& buses, vector<int>& passengers, int capacity) {
        sort(buses.begin(), buses.end());
        sort(passengers.begin(), passengers.end());
        
        int n = buses.size(), m = passengers.size();
        vector<vector<int>> bus_passengers(n);
        int j = 0;
        
        // 模拟每辆公交车的载客过程
        for (int i = 0; i < n; i++) {
            int count = 0;
            while (j < m && passengers[j] <= buses[i] && count < capacity) {
                bus_passengers[i].push_back(passengers[j]);
                j++;
                count++;
            }
        }
        
        // 从最后一辆车开始寻找最晚时间
        for (int i = n - 1; i >= 0; i--) {
            int latest_time;
            
            // 如果这辆车没满，可以在发车时间到达
            if (bus_passengers[i].size() < capacity) {
                latest_time = buses[i];
            } else {
                // 如果满了，尝试挤掉最后一个乘客
                latest_time = bus_passengers[i].back() - 1;
            }
            
            // 检查是否与其他乘客时间冲突
            set<int> passenger_set(passengers.begin(), passengers.end());
            while (passenger_set.count(latest_time)) {
                latest_time--;
            }
            
            // 确保时间有效
            if (latest_time > 0) {
                return latest_time;
            }
        }
        
        return 1;
    }
};

class Solution:
    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:
        buses.sort()
        passengers.sort()
        
        n, m = len(buses), len(passengers)
        bus_passengers = [[] for _ in range(n)]
        j = 0
        
        # 模拟每辆公交车的载客过程
        for i in range(n):
            count = 0
            while j < m and passengers[j] <= buses[i] and count < capacity:
                bus_passengers[i].append(passengers[j])
                j += 1
                count += 1
        
        # 从最后一辆车开始寻找最晚时间
        passenger_set = set(passengers)
        
        for i in range(n - 1, -1, -1):
            # 如果这辆车没满，可以在发车时间到达
            if len(bus_passengers[i]) < capacity:
                latest_time = buses[i]
            else:
                # 如果满了，尝试挤掉最后一个乘客
                latest_time = bus_passengers[i][-1] - 1
            
            # 检查是否与其他乘客时间冲突
            while latest_time in passenger_set:
                latest_time -= 1
            
            # 确保时间有效
            if latest_time > 0:
                return latest_time
        
        return 1

public class Solution {
    public int LatestTimeCatchTheBus(int[] buses, int[] passengers, int capacity) {
        Array.Sort(buses);
        Array.Sort(passengers);
        
        int n = buses.Length, m = passengers.Length;
        List<List<int>> busPassengers = new List<List<int>>();
        for (int i = 0; i < n; i++) {
            busPassengers.Add(new List<int>());
        }
        
        int j = 0;
        
        // 模拟每辆公交车的载客过程
        for (int i = 0; i < n; i++) {
            int count = 0;
            while (j < m && passengers[j] <= buses[i] && count < capacity) {
                busPassengers[i].Add(passengers[j]);
                j++;
                count++;
            }
        }
        
        // 从最后一辆车开始寻找最晚时间
        HashSet<int> passengerSet = new HashSet<int>(passengers);
        
        for (int i = n - 1; i >= 0; i--) {
            int latestTime;
            
            // 如果这辆车没满，可以在发车时间到达
            if (busPassengers[i].Count < capacity) {
                latestTime = buses[i];
            } else {
                // 如果满了，尝试挤掉最后一个乘客
                latestTime = busPassengers[i][busPassengers[i].Count - 1] - 1;
            }
            
            // 检查是否与其他乘客时间冲突
            while (passengerSet.Contains(latestTime)) {
                latestTime--;
            }
            
            // 确保时间有效
            if (latestTime > 0) {
                return latestTime;
            }
        }
        
        return 1;
    }
}

/**
 * @param {number[]} buses
 * @param {number[]} passengers
 * @param {number} capacity
 * @return {number}
 */
var latestTimeCatchTheBus = function(buses, passengers, capacity) {
    buses.sort((a, b) => a - b);
    passengers.sort((a, b) => a - b);
    
    const n = buses.length, m = passengers.length;
    const busPassengers = Array(n).fill().map(() => []);
    let j = 0;
    
    // 模拟每辆公交车的载客过程
    for (let i = 0; i < n; i++) {
        let count = 0;
        while (j < m && passengers[j] <= buses[i] && count < capacity) {
            busPassengers[i].push(passengers[j]);
            j++;
            count++;
        }
    }
    
    // 从最后一辆车开始寻找最晚时间
    const passengerSet = new Set(passengers);
    
    for (let i = n - 1; i >= 0; i--) {
        let latestTime;
        
        // 如果这辆车没满，可以在发车时间到达
        if (busPassengers[i].length < capacity) {
            latestTime = buses[i];
        } else {
            // 如果满了，尝试挤掉最后一个乘客
            latestTime = busPassengers[i][busPassengers[i].length - 1] - 1;
        }
        
        // 检查是否与其他乘客时间冲突
        while (passengerSet.has(latestTime)) {
            latestTime--;
        }
        
        // 确保时间有效
        if (latestTime > 0) {
            return latestTime;
        }
    }
    
    return 1;
};

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

复杂度分析

复杂度类型	复杂度
时间复杂度	O(n log n + m log m)
空间复杂度	O(n + m)

说明：

时间复杂度：主要消耗在排序上，O(n log n + m log m)，其中 n 是公交车数量，m 是乘客数量
空间复杂度：需要额外空间存储每辆车的乘客信息和乘客时间集合，为 O(n + m)

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目