Skip to content

2332. The Latest Time to Catch a Bus 👎

  • Time: $O(\texttt{sort}(\texttt{buses}) + \texttt{sort}(\texttt{passengers}))$
  • Space: $O(\texttt{sort}(\texttt{buses}) + \texttt{sort}(\texttt{passengers}))$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
 public:
  int latestTimeCatchTheBus(vector<int>& buses, vector<int>& passengers,
                            int capacity) {
    ranges::sort(buses);
    ranges::sort(passengers);

    if (passengers.front() > buses.back())
      return buses.back();

    int ans = passengers[0] - 1;
    int i = 0;  // buses' index
    int j = 0;  // passengers' index

    while (i < buses.size()) {
      // Greedily make passengers catch `buses[i]`.
      int arrived = 0;
      while (arrived < capacity && j < passengers.size() &&
             passengers[j] <= buses[i]) {
        if (j > 0 && passengers[j] != passengers[j - 1] + 1)
          ans = passengers[j] - 1;
        ++j;
        ++arrived;
      }
      // There's room for `buses[i]` to carry a passenger arriving at
      // `buses[i]`.
      if (arrived < capacity && j > 0 && passengers[j - 1] != buses[i])
        ans = buses[i];
      ++i;
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
  public int latestTimeCatchTheBus(int[] buses, int[] passengers, int capacity) {
    Arrays.sort(buses);
    Arrays.sort(passengers);

    if (passengers[0] > buses[buses.length - 1])
      return buses[buses.length - 1];

    int ans = passengers[0] - 1;
    int i = 0; // buses' index
    int j = 0; // passengers' index

    while (i < buses.length) {
      // Greedily make passengers catch `buses[i]`.
      int arrived = 0;
      while (arrived < capacity && j < passengers.length && passengers[j] <= buses[i]) {
        if (j > 0 && passengers[j] != passengers[j - 1] + 1)
          ans = passengers[j] - 1;
        ++j;
        ++arrived;
      }
      // There's room for `buses[i]` to carry a passenger arriving at the
      // `buses[i]`.
      if (arrived < capacity && j > 0 && passengers[j - 1] != buses[i])
        ans = buses[i];
      ++i;
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution:
  def latestTimeCatchTheBus(
      self,
      buses: list[int],
      passengers: list[int],
      capacity: int,
  ) -> int:
    buses.sort()
    passengers.sort()

    if passengers[0] > buses[-1]:
      return buses[-1]

    ans = passengers[0] - 1
    i = 0  # buses' index
    j = 0  # passengers' index

    while i < len(buses):
      # Greedily make passengers catch `buses[i]`.
      arrived = 0
      while arrived < capacity and j < len(passengers) and passengers[j] <= buses[i]:
        if j > 0 and passengers[j] != passengers[j - 1] + 1:
          ans = passengers[j] - 1
        j += 1
        arrived += 1
      # There's room for `buses[i]` to carry a passenger arriving at the
      # `buses[i]`.
      if arrived < capacity and j > 0 and passengers[j - 1] != buses[i]:
        ans = buses[i]
      i += 1

    return ans