题目：

给你一个下标从 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 位乘客。
注意你不能跟其他乘客同一时间到达，所以你必须在第二位乘客之前到达。

思路

这个题目相当恶心。当时想到了两种做法，一种是贪心，也是题解的方法，但是想到一个精妙的模型进行抽象，只能不断的补逻辑漏洞。还有一种是二分法。

二分法没有尝试，我看题解有的。

解法1 自己尝试出来的

自己的贪心写法试了很多次，大思路是对的，但是就是有考虑不全的地方

乘客是从小到大排序的，汽车也是从小到大排序的。
当乘客上车不能满足当前汽车cur需求，就需要切换到下一辆next
然后对cur进行求解。 汽车cur的求解分3种情况。
第一种，没有人，就是取汽车出发时间作为最大值，
第二种没有坐满人，这时候需要从出发时间倒退，如果说出发时间20，乘客没有20，就是取20，乘客有20，就需要找有无乘客是19出发的，如果没有，19就可以作为出发点。必然可以更新最大值。
第三种，坐满了人，其实还是从后往前推，看看能不能挤进来座位。（区别上一种可以直接从汽车出发点逆推）
特殊情况，第一个乘客赶不上最后的车，贪心最后一辆车的出发时间
if (passengers[0] > buses[buses.length - 1]) { return buses[buses.length - 1]; }
另外还有考虑，车发完了，人还没有完，提前返回，人发完了，车还没有结算，继续结算
还有最小值从 int max = passengers[0] - 1 第一个乘客减1开始搭配 max = Math.max(max, buses[j]); 是因为坐满的逻辑有缺陷，需要补上一位 比如。满车 10，11，12 看看能不能补上贪心9 因为没有考虑到，所以才有这么丑陋的代码

总之方向是对的，但是自己思考的贪心的逻辑是混乱的

public static int latestTimeCatchTheBus(int[] buses, int[] passengers, int capacity) {Arrays.sort(buses);Arrays.sort(passengers);// 如果第一个乘客赶不上最后一班车。那么直接返回最后一班车的时间if (passengers[0] > buses[buses.length - 1]) {return buses[buses.length - 1];}int max = passengers[0] - 1;int j = 0;List<Integer> list = new ArrayList<>();for (int i = 0; i < passengers.length; i++) {int passenger = passengers[i];while (buses[j] < passenger || list.size() == capacity) {  // 时间上不合适，寻找下一辆车// 如果满员if (capacity == list.size()) {// 看一下前面有没有空间可以插入for (int k = 0; k < list.size(); k++) {Integer pre = list.get(k);if (pre > 0 && passengers[pre - 1] + 1 < passengers[pre]) {max = passengers[pre] - 1;  }}list = new ArrayList<>();} else if (list.isEmpty()) {// 如果汽车上是空的话，就是说我要贪心坐上这辆车出发的时间max = Math.max(max, buses[j]); } else { // 如果没有满员 或者如果为空。没有满员但是是掐点到的。// 从后往前遍历。int need = buses[j];int flag = 0;for (int k = list.size() - 1; k >= 0; k--) {Integer i1 = list.get(k);if (passengers[i1] != need) {max = need;flag = 1;break;}need--;}if (flag == 0 && list.get(0) > 0 && passengers[list.get(0) - 1] + 1 != passengers[list.get(0)]) {max = need;}list = new ArrayList<>();}j++;// 如何结算if (j == buses.length) {return max;}}list.add(i);}// 最后还要再结算一次if (capacity == list.size()) { // 如果满员//  看一下前面有没有空间可以插入for (int k = 0; k < list.size(); k++) {Integer pre = list.get(k);if (pre > 0 && passengers[pre - 1] + 1 < passengers[pre]) {max = passengers[pre] - 1; // 更新first,可以放在最前面}}j++;} else if (list.isEmpty()) {// 如果是空的话，就是说我要坐上这辆车最晚的时间// 20点的车  就20点上车max = Math.max(max, buses[j]);j++;} else { // 如果没有满员 或者如果为空。没有满员但是是掐点到的。// 从后往前遍历。int need = buses[j];int flag = 0;for (int k = list.size() - 1; k >= 0; k--) {Integer i1 = list.get(k);if (passengers[i1] != need) {max = need;flag = 1;break;}need--;}if (flag == 0 && list.get(0) > 0 && passengers[list.get(0) - 1] + 1 != passengers[list.get(0)]) {max = need;}j++;}// 如果汽车没有遍历完，遍历汽车while (j < buses.length) {max = Math.max(max, buses[j]);j++;}return max;}

解法2 官方的

先不断的塞人
如果说。到了最后一辆车，人都挤满了。刚好挤满。就顺着人倒退，找第一个出现的空隙。（比如，乘客有 22，21，20，19，17 就可以找到空袭18返回）
如果没有坐满，直接返回最后一辆车的数值

public int latestTimeCatchTheBus2(int[] buses, int[] passengers, int capacity) {Arrays.sort(buses);Arrays.sort(passengers);int pos = 0;int space = 0;for (int arrive : buses) {space = capacity;while (space > 0 && pos < passengers.length && passengers[pos] <= arrive) {space--;pos++;}}pos--;// space多余0 说明还有位置，就去最后一班车。否则，说明没有空位，只能倒推int lastCatchTime = space > 0 ? buses[buses.length - 1] : passengers[pos];while (pos >= 0 && passengers[pos] == lastCatchTime) {pos--;lastCatchTime--;}return lastCatchTime;}// 如果有空隙可以直接进去。如果没有空袭，需要从后往前遍历

总结

这就像是初级程序员和高级程序员写业务代码。高级程序员直核心，逻辑简单明了。初级程序员逻辑弯弯绕绕，各种变量，各种补丁，无用的判断分支。