【每日一题】LeetCode 2332.坐上公交的最晚时间（数组、双指针、二分查找、排序）

【每日一题】LeetCode 2332.坐上公交的最晚时间（数组、双指针、二分查找、排序）

题目描述

给你一个下标从 0 开始长度为 n 的整数数组 buses ，其中 buses[i] 表示第 i 辆公交车的出发时间。同时给你一个下标从 0 开始长度为 m 的整数数组 passengers ，其中 passengers[j] 表示第 j 位乘客的到达时间。所有公交车出发的时间互不相同，所有乘客到达的时间也互不相同。

给你一个整数 capacity ，表示每辆公交车 最多 能容纳的乘客数目。

每位乘客都会搭乘下一辆有座位的公交车。如果你在 y 时刻到达，公交在 x 时刻出发，满足 y <= x 且公交没有满，那么你可以搭乘这一辆公交。最早 到达的乘客优先上车。

返回你可以搭乘公交车的最晚到达公交站时间。你 不能 跟别的乘客同时刻到达。

**注意：**数组 buses 和 passengers 不一定是有序的。

思路分析

1. 排序：首先对 buses 和 passengers 数组进行排序，这样可以方便我们按照时间顺序处理乘客和公交车。
2. 遍历：遍历 buses 数组，对于每一辆公交车，检查在当前公交车出发时间之前到达的乘客数量，直到公交车满员或者所有乘客都已经被处理。
3. 计算最晚到达时间：在遍历过程中，我们需要记录下在每辆公交车出发之前能够搭载的最后一个乘客的时间。这个时间点就是我们的候选答案。
4. 调整时间：由于乘客不能与他人同时到达，我们需要在找到的候选答案基础上继续向前寻找，直到找到一个没有乘客到达的时间点，这个时间点就是我们可以返回的最晚到达时间。

输入示例

示例 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 中的元素 互不相同 。

代码实现

import java.util.Arrays;

class Solution {
    public int latestTimeCatchTheBus(int[] buses, int[] passengers, int capacity) {
        // 对公交车和乘客的时间进行排序
        Arrays.sort(buses);
        Arrays.sort(passengers);

        int j = 0;  // 用于指向乘客数组
        int c = 0;  // 当前车辆的剩余容量

        // 遍历每一班公交车的时间
        for (int i = 0; i < buses.length; i++) {
            // 检查当前公交车在出发前能搭载的乘客数量
            while (c < capacity && j < passengers.length && passengers[j] <= buses[i]) {
                j++; // 当前乘客上车，指向下一个乘客
                c++; // 减少当前车辆的剩余容量
            }
        }

        // 找到插队的最佳时机
        j--; // 上一步中 j 可能超出乘客数组的索引，需要回到最后一位有效乘客
        int ans = c > 0 ? buses[buses.length - 1] : passengers[j]; // 如果最后一班车还有空位，最新的时间点就是最后一班车的时间；否则要找到一个乘客离开的时间点

        // 如果乘客离开时间点与我们选择的时间点相同，则需要往前寻找
        while (j >= 0 && ans == passengers[j]) {
            ans--; // 往前找没有乘客的时间点
            j--;
        }
        return ans; // 返回最终的时间点
    }
}