坐上公交的最晚时间

2332. 坐上公交的最晚时间

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

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

每位乘客都会搭乘下一辆有座位的公交车。如果你在 y 时刻到达，公交在 x 时刻出发，满足 y <= x 且公交没有满，那么你可以搭乘这一辆公交。最早到达的乘客优先上车。

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

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

示例 1：

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

示例 2：

输入：buses = [20,30,10], passengers = [19,13,26,4,25,11,21], capacity = 2
输出：20
解释：
第 1 辆公交车载着第 4 位乘客。
第 2 辆公交车载着第 6 位和第 2 位乘客。
第 3 辆公交车载着第 1 位乘客和你。

提示：

n == buses.length
m == passengers.length
1 <= n, m, capacity <= 10⁵
2 <= buses[i], passengers[i] <= 10⁹
buses 中的元素 互不相同 。
passengers 中的元素 互不相同 。

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int latestTimeCatchTheBus(vector<int>& buses, vector<int>& passengers, int capacity) { } };

rust 解法, 执行用时: 26 ms, 内存消耗: 4.2 MB, 提交时间: 2024-09-18 09:31:55

impl Solution {
    pub fn latest_time_catch_the_bus(mut buses: Vec<i32>, mut passengers: Vec<i32>, capacity: i32) -> i32 {
        buses.sort_unstable();
        passengers.sort_unstable();

        // 模拟乘客上车
        let mut j = 0;
        let mut c = 0;
        for &t in &buses {
            c = capacity;
            while c > 0 && j < passengers.len() && passengers[j] <= t {
                j += 1;
                c -= 1;
            }
        }

        // 寻找插队时机
        j -= 1;
        let mut ans = if c > 0 { *buses.last().unwrap() } else { passengers[j] };
        while j < passengers.len() && ans == passengers[j] {
            ans -= 1; // 往前找没人到达的时刻
            j -= 1;
        }
        ans
    }
}

javascript 解法, 执行用时: 188 ms, 内存消耗: 65.5 MB, 提交时间: 2024-09-18 09:31:42

/**
 * @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);

    // 模拟乘客上车
    let j = 0, c;
    for (const t of buses) {
        for (c = capacity; c > 0 && j < passengers.length && passengers[j] <= t; c--) {
            j++;
        }
    }

    // 寻找插队时机
    j--;
    let ans = c > 0 ? buses[buses.length - 1] : passengers[j];
    while (j >= 0 && ans === passengers[j]) {
        ans--; // 往前找没人到达的时刻
        j--;
    }
    return ans;
};

python3 解法, 执行用时: 144 ms, 内存消耗: 40.1 MB, 提交时间: 2023-06-29 09:29:40

class Solution:
    def latestTimeCatchTheBus(self, buses: List[int], P: List[int], capacity: int) -> int:
        SP = set(P)
        P = deque(sorted(P))
        last = 1
        for t in sorted(buses):
            rest = capacity
            
            while rest and P and P[0]<=t:
                # 取而代之
                last = P.popleft()
                rest -= 1

            if rest:
                # 有空位, 最后一刻坐上去
                last = t
        
        while last in SP:
            last -= 1
        return last

golang 解法, 执行用时: 160 ms, 内存消耗: 9.4 MB, 提交时间: 2023-06-29 09:28:39

func latestTimeCatchTheBus(buses, passengers []int, capacity int) (ans int) {
	sort.Ints(buses)
	sort.Ints(passengers)
	j, c := 0, 0
	for _, t := range buses {
		for c = capacity; c > 0 && j < len(passengers) && passengers[j] <= t; c-- {
			j++
		}
	}
	if c > 0 {
		ans = buses[len(buses)-1] // 最后一班公交还有空位，在它发车时到达
	} else {
		ans = passengers[j-1] // 上一个上车的乘客
	}
	for j--; j >= 0 && passengers[j] == ans; j-- { // 往前找没人到达的时刻
		ans--
	}
	return
}

cpp 解法, 执行用时: 132 ms, 内存消耗: 65.3 MB, 提交时间: 2023-06-29 09:28:21

class Solution {
public:
    int latestTimeCatchTheBus(vector<int> &buses, vector<int> &passengers, int capacity) {
        sort(buses.begin(), buses.end());
        sort(passengers.begin(), passengers.end());
        int j = 0, c;
        for (int t : buses)
            for (c = capacity; c && j < passengers.size() && passengers[j] <= t; --c)
                ++j;
        --j;
        int ans = c ? buses.back() : passengers[j]; // 在发车时到达公交站 or 上一个上车的乘客
        while (j >= 0 && passengers[j--] == ans) --ans; // 往前找没人到达的时刻
        return ans;
    }
};

java 解法, 执行用时: 26 ms, 内存消耗: 53.7 MB, 提交时间: 2023-06-29 09:28:06

class Solution {
    public int latestTimeCatchTheBus(int[] buses, int[] passengers, int capacity) {
        Arrays.sort(buses);
        Arrays.sort(passengers);
        int j = 0, c = 0;
        for (var t : buses)
            for (c = capacity; c > 0 && j < passengers.length && passengers[j] <= t; --c)
                ++j;
        --j;
        var ans = c > 0 ? buses[buses.length - 1] : passengers[j]; // 在发车时到达公交站 or 上一个上车的乘客
        while (j >= 0 && passengers[j--] == ans) --ans; // 往前找没人到达的时刻
        return ans;
    }
}

python3 解法, 执行用时: 148 ms, 内存消耗: 35.4 MB, 提交时间: 2023-06-29 09:27:44

'''
脑筋急转弯

排序后，用双指针模拟乘客上车的过程：遍历公交车，找哪些乘客可以上车（先来先上车）。

模拟结束后：
如果最后一班公交还有空位，我们可以在发车时到达公交站，如果此刻有人，我们可以顺着他往前找到没人到达的时刻；
如果最后一班公交没有空位，我们可以找到上一个上车的乘客，顺着他往前找到一个没人到达的时刻。
这里可以「插队」的理由是，如果一个乘客上了车，那么他前面的乘客肯定也上了车（因为先来先上车）。
'''
class Solution:
    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:
        buses.sort()
        passengers.sort()
        j = 0
        for t in buses:
            c = capacity
            while c and j < len(passengers) and passengers[j] <= t:
                c -= 1
                j += 1
        j -= 1
        ans = buses[-1] if c else passengers[j]  # 在发车时到达公交站 or 上一个上车的乘客
        while j >= 0 and passengers[j] == ans:  # 往前找没人到达的时刻
            ans -= 1
            j -= 1
        return ans

上一题

下一题

详情