人话题意：你是一个懒惰的人，虽然你要赶公交车，但你想多睡会，恰好你知道每辆车的发车时间buses和每辆车容capacity，和每个乘客乘车的时间passenger，旨在求可以赶上公交车的最晚出发时间。
思路一：二分答案
求最晚能满足赶上公交的时间，可以发现答案具有二分性，比这个时间早一定赶得上公交，比这个时间晚就赶不上。
二分的关键在于寻找循环不变量，下界指向满足要求的，上界指向不满足要求的，这里我才用开区间写法(l, r),可以简化代码书写。
根据提示， 2 < p a s s e n g e r [ i ] < 1 0 9 2< passenger[i] < 10^9 2<passenger[i]<109因此在1时刻之前出发都是满足要求的，所以初始l = 0，指向的时刻是满足要求的。乘客最晚时间 1 0 9 10^9 109,我们取开区间 + 1即可。接下来是check函数，我们只需要把我们的时刻添加到passenger中，再模拟 bus能承载的数量之内即满足要求
每次使用check函数都会创建一个数组，而且check函数两层循环，所以不管是时间还是空间复杂度都很高。
class Solution {
public:
bool check(int time, vector<int>& buses, vector<int>& passengers, int capacity) {
auto v = passengers;
v.push_back(time);
//基本有序可以使用插入排序
ranges::sort(v);
int j = 0;
for(int t : buses)
{
for(int x = 0; j <= passengers.size() && v[j] <= t && x < capacity; ++x, ++j)
{
if(v[j] >= time) return true;
}
}
return false;
}
int latestTimeCatchTheBus(vector<int>& buses, vector<int>& passengers, int capacity) {
ranges::sort(buses);
ranges::sort(passengers);
int l = 0 , r = 1e9 + 1;
while(l + 1 < r)
{
int mid = ((r - l + 1)>>1) + l;
(check(mid, buses, passengers,capacity) ? l : r) = mid;
}
unordered_set<int> s;
for (auto &x : passengers) s.insert(x);
while (s.count(l)) {
--l;
}
return l;
}
};
思路二：贪心双指针
最晚出发，那我们就先考虑赶最晚那一趟车的最后一个到
- 如果最后那趟车没有满，那就无需插队，排到末尾，只要赶在公交车出发前到就行
- 如果满了那我们就赶在最后那个人之前到就行，此时再根据题目要求不能和其他乘客同时到，向前不断寻找没人到达的时刻进行插队即可。
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 x : buses)
{
for(c = capacity; c && j < passengers.size() &&passengers[j] <= x; c--)
{
j++;
}
}
j--;
//判断最后那趟车是否满，不满的话就赶在公交车出发之前到即可，满的话就进行插队，初始为最后那个人的时刻
int ans = c ? buses.back() : passengers[j];
while (j >= 0 && ans == passengers[j]) {
ans--; // 往前找没人到达的时刻
j--;
}
return ans;
}
};