模拟+分类讨论，LeetCode 2332. 坐上公交的最晚时间

一、题目

1、题目描述

2、接口描述

python3

 ​

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

cpp

 ​

class Solution {
public:
    int latestTimeCatchTheBus(vector<int>& buses, vector<int>& passengers, int capacity) {
        
    }
};

C#

 ​

public class Solution {
    public int LatestTimeCatchTheBus(int[] buses, int[] passengers, int capacity) {

    }
}

3、原题链接

二、解题报告

1、思路分析

将车 和 乘客都升序排序

随着来的乘客越来越晚，其能登上的车也就越靠后

考虑双指针

遍历每个车，维护一个乘客指针，只要当前乘客能上车就后移

结束后，如果最后一个车没满，那么从最后一个车的发车时间往前倒推，找到一个空闲时间点

否则，从最后一个上车的乘客往前倒推，找到一个空闲时间点

由于最多倒推 len(p[assengers) 次，所以可行

2、复杂度

时间复杂度： O(nlogn + mlogn)空间复杂度：O(1)

3、代码详解

python3

 ​

class Solution:
    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:
        buses.sort()
        passengers.sort()
        cur = cnt = 0
        for x in buses:
            cnt = capacity
            while cur < len(passengers) and cnt and x >= passengers[cur]:
                cur += 1
                cnt -= 1
        cur -= 1
        res = buses[-1] if cnt else passengers[cur]
        while cur >= 0 and res == passengers[cur]:
            res -= 1
            cur -= 1
        return res

cpp

 ​

class Solution {
public:
    int latestTimeCatchTheBus(vector<int>& buses, vector<int>& passengers, int capacity) {
        std::ranges::sort(buses), std::ranges::sort(passengers);
        int cnt = capacity, cur = 0;
        for (int x : buses) {
            cnt = capacity;
            while (cur < passengers.size() && cnt > 0 && x >= passengers[cur])
                ++cur, --cnt;
        }
        --cur;
        int res = cnt > 0 ? buses.back() : passengers[cur];
        while (cur >= 0 && res == passengers[cur])
        {
            --res;
            --cur;
        }
        return res;
    }
};

C#

 ​

public class Solution
{
    public int LatestTimeCatchTheBus(int[] buses, int[] passengers, int capacity)
    {
        Array.Sort(buses);
        Array.Sort(passengers);
        int cur = 0, cnt = 0;
        foreach(int x in buses)
        {
            cnt = capacity;
            while (cur < passengers.Length && cnt > 0 && x >= passengers[cur])
            {
                ++cur;
                --cnt;
            }
        }
        --cur;
        int res = cnt > 0 ? buses[buses.Length - 1] : passengers[cur];
        while (cur >= 0 && res == passengers[cur])
        {
            --res;
            --cur;
        }
        return res;
    }
}