2332-坐上公交的最晚时间

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:32 2023-09-13 16:06:32 Updated    

给你一个下标从 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 <= 105
  • 2 <= buses[i], passengers[i] <= 109
  • buses 中的元素 **互不相同 **。
  • passengers 中的元素 互不相同 。

本题 视频讲解 已出炉，欢迎点赞三连~

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

模拟结束后：

  • 如果最后一班公交还有空位，我们可以在发车时到达公交站，如果此刻有人，我们可以顺着他往前找到没人到达的时刻；
  • 如果最后一班公交没有空位，我们可以找到上一个上车的乘客，顺着他往前找到一个没人到达的时刻。

这里可以「插队」的理由是，如果一个乘客上了车，那么他前面的乘客肯定也上了车（因为先来先上车）。

复杂度分析

  • 时间复杂度：O(n\log n+m\log m)。瓶颈在排序上。
  • 空间复杂度：O(1)。忽略排序的栈开销。
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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;
    }
};
[sol1-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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
}
 Comments
On this page
2332-坐上公交的最晚时间