【LeetCode】2332. 坐上公交的最晚时间

LeetCode 2332. 坐上公交的最晚时间

题目描述

详细的题目描述可见LeetCode对应的原题目。

简单来说，给定 $A$ 数组[10, 20]和 $B$ 数组[2, 17, 18, 19]，数组A表示公交车的到达时间，B表示乘客到达车站的时间，还给定一个公交车的容量capacity，假定为 $2$ ，问乘客最晚在何时到达可以乘坐公交车。

显然对于上述样例，在t=10之前达到的只有2时刻到达的乘客，因此第一辆车在t=10出发，只携带第一个到达的乘客（显然，第一辆车有一个空位，因为公交车的容量为 $2$ ）。而第二辆车驶离的时间是t=20，在此之前还未离开且到达的乘客分别在t=17/18/19到达，只有t=17/18到达的乘客可以离开，因为公交车的容量为 $2$ 。

对于上述样例，乘客可行的最晚到达时间是t=16，因为题目要求乘客的到达时间不可重复，公交车的驶离时间也是不重复的。

思路

拿到这道题目给我的第一感觉就是双指针，解决该问题也确实用到了双指针，但是五分钟内没想出来，参考了题解，发现自己确实遗漏了一些细节，遂在此对整题的思路进行记录。

首先，可以对公交车的驶离时间和乘客的到达时间进行一下排序，因为初始的输入可能是无序的，但数组中的元素应该是有序的。

之后，便可以开始设计算法解决这道题目。

此处使用双指针，一个指针arrive指向公交车驶离时间的数组buses，而另一个指针pos指向乘客的到达时间数组passengers。对每一个公交车驶离的时间进行遍历，在遍历的每一步当中，需要对乘客到达时间的指针进行修改。在每一次迭代的初始时，设置一个变量space = capacity用于表示当前这辆车还剩下多少个空位。当公交车满载时，即使乘客已经达到也无法上车，按照先来后到没上车的乘客将登上下一辆车。

分析完问题之后，这道题目的双指针更新边界也就非常明朗了，可以抽象为如下代码：

while(space > 0 && pos < passengers.size() && passengers[pos] <= arrive) {space --;	// 当前车辆的位置减一pos ++;		// 满足条件的乘客上车
}

需要注意的是条件pos < passengers.size()一定是在passengers[pos] <= arrive之前的，因为按照C/C++条件运算符的优先级，对于&&运算，从左至右只要有一个条件不满足，那么直接返回false，如果先判断passengers[pos] <= arrive的话，此时的pos可能越界，即已经遍历完所有的passengers了。

下一步是对答案就行更新。乘客的最晚到达时间分为两种情况，第一种情况是最后一辆车还没有坐满，这是最理想的情况，乘客直接在最后一辆车的驶离时刻到达即可。第二种情况较为复杂，即最后一辆车也坐满了，它的最晚到达时间只能早于passengers当中从后往前找到的某个值，可以先令它为passengers[pos]，再向前找到满足条件的值。

需要注意的是，根据刚才的分析，指针pos会指向满足迭代条件的下一个值（因为这样才会使循环达到条件而停止），因此在对答案进行更新之前需要先对pos --。

最后一辆车的剩余位置为space，按照刚才的分析，答案res = buses.back() if space > 0 else passengers[pos]。如果res = passengers[pos]，由于题目要求乘客不能同时到达，必须向前寻找满足条件的值，由于乘客在passengers中可能接连到达，因此使用下述逻辑来得到最终的res：

while(pos >= 0 && passengers[pos] == res) {res --;pos --;
}

此处使用pos >= 0不必考虑边界情况，因为题目要求中明确指出passengers的值不会小于 $2$ ，意味着res最晚也可以是 $1$ 。

C++的完整实现如下：

class Solution {
public:int latestTimeCatchTheBus(vector<int>& buses, vector<int>& passengers, int capacity) {sort(passengers.begin(), passengers.end());sort(buses.begin(), buses.end());int pos = 0;int space = 0;for(int arrive: buses) {space = capacity;while(space > 0 && pos < passengers.size() && passengers[pos] <= arrive) {pos ++;space --;}}pos --;int res = space > 0 ? buses.back() : passengers[pos];while(pos >= 0 && res == passengers[pos]) {res --;pos --;}return res;}
};

Go的实现如下：

func latestTimeCatchTheBus(buses []int, passengers []int, capacity int) int {sort.Ints(buses)sort.Ints(passengers)space, pos := 0, 0for _, arrive := range(buses) {space = capacityfor space > 0 && pos < len(passengers) && passengers[pos] <= arrive {space --pos ++}}pos --res := buses[len(buses)-1]if space <= 0 {res = passengers[pos]}for pos >= 0 && res == passengers[pos] {pos --res --}return res
}