Powered by:NEFU AB-IN

Link

2332. 坐上公交的最晚时间

题意

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

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

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

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

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

思路

首先一遍扫过去，找到最后一班车，尽量每个车坐满（不能用二分找，会T），设定一个指针从开始扫到结尾
然后如果没坐满，那么最晚的时间是车来的时间；如果坐满了，挤下去最后一个人

代码

# 3.8.9 import
# ————————————————————— Division line ——————————————————————


class Solution:
    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:
        buses.sort()
        passengers.sort()

        set_ = set(passengers)

        l = 0
        for bus in buses:
            length = capacity
            while length and l < len(passengers) and passengers[l] <= bus:
                length -= 1
                l += 1
        
        for i in range(buses[-1] if length else passengers[l - 1], -1, -1):
            if i not in set_:
                return i