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
class Solution {
 public:
  int latestTimeCatchTheBus(vector<int>& buses, vector<int>& passengers,
                            int capacity) {
    sort(buses.begin(), buses.end());
    sort(passengers.begin(), passengers.end());

    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
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 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
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 buses[i]
      if arrived < capacity and j > 0 and passengers[j - 1] != buses[i]:
        ans = buses[i]
      i += 1

    return ans