坐上公交的最晚时间

标签: 数组 双指针 二分查找 排序

难度: Medium

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

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

Submission

运行时间: 102 ms

内存: 34.5 MB

class Solution:
    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:
        buses.sort()
        passengers.sort()
        R = 0
        n = len(passengers)
        for L in buses:
            cnt = 0
            while R < n and cnt < capacity and passengers[R] <= L:
                R += 1
                cnt += 1

        if cnt < capacity:
            ans = buses[-1]
            R -= 1
        else:
            ans = passengers[R-1]-1
            R -= 2
        while R >= 0 and ans == passengers[R]:
            ans -= 1
            R -= 1
        return ans

Explain

首先，对公交车和乘客的到达时间进行排序，确保处理时是按时间顺序进行的。然后，使用一个指针 R 遍历乘客数组，另外通过外层循环遍历每辆公交车。对于每辆公交车，我们检查如果当前乘客的到达时间小于等于该公交车的出发时间，并且该车还有空位，那么该乘客可以乘坐这辆公交车。在处理完所有公交车后，检查最后一辆公交车是否还有空位。如果有，最晚的时间就是这辆公交车的出发时间；如果没有空位，那么最晚时间应该是最后一个上车乘客的到达时间前一分钟。考虑到不能与其他乘客同时到达，我们在得到可能的最晚时间后，向前搜索直到找到一个不与任何乘客到达时间重合的时刻。

时间复杂度: O(m log m + n log n)

空间复杂度: O(log m + log n)

class Solution:
    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:
        buses.sort()  # 对公交车出发时间进行排序
        passengers.sort()  # 对乘客到达时间进行排序
        R = 0  # 用于遍历乘客的指针
        n = len(passengers)
        for L in buses:  # 遍历每辆公交车
            cnt = 0  # 当前公交车已载乘客数
            while R < n and cnt < capacity and passengers[R] <= L:  # 乘客能上这辆公交车
                R += 1  # 移动乘客指针
                cnt += 1  # 增加乘客数

        if cnt < capacity:  # 最后一辆公交车还有空位
            ans = buses[-1]  # 可以在公交车出发时到达
            R -= 1
        else:  # 没有空位
            ans = passengers[R-1]-1  # 最晚到达时间是最后一个乘客到达时间的前一分钟
            R -= 2
        while R >= 0 and ans == passengers[R]:  # 确保不与其他乘客同时到达
            ans -= 1  # 向前移动一分钟
            R -= 1
        return ans  # 返回最晚到达时间