当前位置：首页 > news >正文

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

news 来源：原创 2024/9/20 4:38:39

一、题目

1、题目描述

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

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

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

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

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

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、原题链接

2332. The Latest Time to Catch a Bus

二、解题报告

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 = 0for x in buses:cnt = capacitywhile cur < len(passengers) and cnt and x >= passengers[cur]:cur += 1cnt -= 1cur -= 1res = buses[-1] if cnt else passengers[cur]while cur >= 0 and res == passengers[cur]:res -= 1cur -= 1return 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;}
}