力扣（leetcode）每日一题 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 位乘客。
注意你不能跟其他乘客同一时间到达，所以你必须在第二位乘客之前到达。

思路

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

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

解法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;
    }
    // 如果有空隙可以直接进去。如果没有空袭，需要从后往前遍历

总结

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

原文地址：https://blog.csdn.net/ganjiee0007/article/details/142407629

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！