Question

2332. 坐上公交的最晚时间

English Version

题目描述

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

解法

方法一：模拟

我们先排序，然后用双指针模拟乘客上车的过程：遍历公交车 $bus$，乘客遵循“先到先上车”的原则。

模拟结束后，判断最后一班公交车是否还有空位：

• 若有空位，我们可以在公交车发车时 $bus[|bus|-1]$ 到达公交站；若此时有人，可以顺着往前找到没人到达的时刻；
• 若无空位，我们可以找到上一个上车的乘客，顺着他往前找到没人到达的时刻。

时间复杂度 $O(n \times \log n + m \times \log m)$，空间复杂度 $O(\log n + \log m)$。其中 $n$ 和 $m$ 分别是公交车和乘客的数量。

class Solution:
  def latestTimeCatchTheBus(
    self, buses: List[int], passengers: List[int], capacity: int
  ) -> int:
    buses.sort()
    passengers.sort()
    j = 0
    for t in buses:
      c = capacity
      while c and j < len(passengers) and passengers[j] <= t:
        c, j = c - 1, j + 1
    j -= 1
    ans = buses[-1] if c else passengers[j]
    while ~j and passengers[j] == ans:
      ans, j = ans - 1, j - 1
    return ans

class Solution {
  public int latestTimeCatchTheBus(int[] buses, int[] passengers, int capacity) {
    Arrays.sort(buses);
    Arrays.sort(passengers);
    int j = 0, c = 0;
    for (int t : buses) {
      c = capacity;
      while (c > 0 && j < passengers.length && passengers[j] <= t) {
        --c;
        ++j;
      }
    }
    --j;
    int ans = c > 0 ? buses[buses.length - 1] : passengers[j];
    while (j >= 0 && ans == passengers[j]) {
      --ans;
      --j;
    }
    return ans;
  }
}

class Solution {
public:
  int latestTimeCatchTheBus(vector<int>& buses, vector<int>& passengers, int capacity) {
    sort(buses.begin(), buses.end());
    sort(passengers.begin(), passengers.end());
    int j = 0, c = 0;
    for (int t : buses) {
      c = capacity;
      while (c && j < passengers.size() && passengers[j] <= t) --c, ++j;
    }
    --j;
    int ans = c ? buses[buses.size() - 1] : passengers[j];
    while (~j && ans == passengers[j]) --j, --ans;
    return ans;
  }
};

func latestTimeCatchTheBus(buses []int, passengers []int, capacity int) int {
  sort.Ints(buses)
  sort.Ints(passengers)
  j, c := 0, 0
  for _, t := range buses {
    c = capacity
    for c > 0 && j < len(passengers) && passengers[j] <= t {
      j++
      c--
    }
  }
  j--
  ans := buses[len(buses)-1]
  if c == 0 {
    ans = passengers[j]
  }
  for j >= 0 && ans == passengers[j] {
    ans--
    j--
  }
  return ans
}

function latestTimeCatchTheBus(buses: number[], passengers: number[], capacity: number): number {
  buses.sort((a, b) => a - b);
  passengers.sort((a, b) => a - b);
  let [j, c] = [0, 0];
  for (const t of buses) {
    c = capacity;
    while (c && j < passengers.length && passengers[j] <= t) {
      --c;
      ++j;
    }
  }
  --j;
  let ans = c > 0 ? buses.at(-1)! : passengers[j];
  while (j >= 0 && passengers[j] === ans) {
    --ans;
    --j;
  }
  return ans;
}

/**
 * @param {number[]} buses
 * @param {number[]} passengers
 * @param {number} capacity
 * @return {number}
 */
var latestTimeCatchTheBus = function (buses, passengers, capacity) {
  buses.sort((a, b) => a - b);
  passengers.sort((a, b) => a - b);
  let [j, c] = [0, 0];
  for (const t of buses) {
    c = capacity;
    while (c && j < passengers.length && passengers[j] <= t) {
      --c;
      ++j;
    }
  }
  --j;
  let ans = c > 0 ? buses.at(-1) : passengers[j];
  while (j >= 0 && passengers[j] === ans) {
    --ans;
    --j;
  }
  return ans;
};