2332.坐上公交的最晚时间

链接：2332.坐上公交的最晚时间
难度：Medium
标签：数组、双指针、二分查找、排序
简介：返回你可以搭乘公交车的最晚到达公交站时间。

题解 1 - python

• 编辑时间：2024-09-19
• 执行用时：242ms
• 内存消耗：34.53MB
• 编程语言：python
• 解法介绍：贪心的认为1.最迟的时间，一定是某一个行人的前一个2.如果公交车没上满人，那就是公交车的到达时间是最晚时间

class Solution:
    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:
        buses.sort()
        passengers.sort()
        bus_len = len(buses)
        pas_len = len(passengers)
        # print('buses', buses)
        # print('passengers', passengers)
        cur_pre = 0
        pre_arr = [cur_pre] * pas_len
        for pas_idx in range(pas_len):
            if passengers[pas_idx - 1] != passengers[pas_idx] - 1:
                cur_pre = passengers[pas_idx] - 1
            pre_arr[pas_idx] = cur_pre
        # print('pre_arr', pre_arr)
                
        res = 0
        pas_idx = 0
        pas_cnt = 0
        for bus_idx in range(bus_len):
            # print(f'===> bidx = {bus_idx}, pidx = {pas_idx}, res = {res}, pcnt = {pas_cnt}')
            while pas_idx < pas_len and passengers[pas_idx] <= buses[bus_idx] and pas_cnt < capacity:
                if pas_cnt + 1 == capacity:
                    res = pre_arr[pas_idx]
                pas_cnt += 1
                pas_idx += 1
            # print(f'bidx = {bus_idx}, pidx = {pas_idx}, res = {res}, pcnt = {pas_cnt}')
            if pas_cnt < capacity:
                # print("IN")
                if pas_idx > 0 and passengers[pas_idx - 1] != buses[bus_idx] or pas_idx == 0:
                    res = buses[bus_idx]
                elif pas_idx > 0:
                    res = pre_arr[pas_idx - 1]
            pas_cnt -= min(capacity, pas_cnt)
        return res