2332. 坐上公交的最晚时间

题目描述：

给你一个下标从 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 中的元素 互不相同 。

---

解题分析及思路：

方法：模拟

思路：

首先，按照“我”未上车的前提下，让其他乘客按照原有规则上车，到最后一辆车后，“我”需要上最后一辆车，那么存在两种情况：

1. 所有的乘客都上车了，并且还有一个位置让“我”坐，那么“我”是最后一位乘客，“我”的上车时间最晚和最后一辆车的到达时间一样（此前提下，“我”的上车时间不能和之前上车的乘客时间冲突）。
2. 所有的乘客都上车了，但是没有位置让“我”坐，那么“我”是最后一位乘客，“我”的上车时间要比最后一辆车的最后一个乘客上车时间早，我才能顺利上车（此前提下，“我”的上车时间不能和之前上车的乘客时间冲突）。

那么，可以用count记录每辆车上的乘客数目

1. 当count != capacity，说明还有位置让“我”坐，那么“我”的上车时间最晚和最后一辆车的到达时间一样（此前提下，“我”的上车时间不能和之前上车的乘客时间冲突）。
2. 当count == capacity，说明车上位置已经满了，那么“我”的上车时间要比最后一辆车的最后一个乘客上车时间早，我才能顺利上车（此前提下，“我”的上车时间不能和之前上车的乘客时间冲突）。

为避免“我”的上车时间和之前上车的乘客时间冲突，需要将乘客按照到达时间排序，同时将公交车按照出发时间排序。

func latestTimeCatchTheBus(buses []int, passengers []int, capacity int) int {
	sort.Ints(buses)
	sort.Ints(passengers)
	var buseIndex int
	var passengerIndex int
	var count int
	for ; buseIndex < len(buses); buseIndex++ {
		count = 0
		for count < capacity && passengerIndex < len(passengers) && buses[buseIndex] >= passengers[passengerIndex] {
			count++
			passengerIndex++
		}
	}
	ans := buses[len(buses)-1]
	passengerIndex--
	if count == capacity {
		ans = passengers[passengerIndex]
	}
	for passengerIndex >= 0 && ans == passengers[passengerIndex] {
		ans--
		passengerIndex--
	}
	return ans
}

复杂度：

• 时间复杂度：O(n)
• 空间复杂度：O(1)

执行结果：

• 执行耗时:115 ms,击败了16.67% 的Go用户
• 内存消耗:8.9 MB,击败了75.00% 的Go用户