Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2332.html
2332. The Latest Time to Catch a Bus
- Difficulty: Medium.
- Related Topics: Array, Two Pointers, Binary Search, Sorting.
- Similar Questions: Minimum Speed to Arrive on Time.
Problem
You are given a 0-indexed integer array buses of length n, where buses[i] represents the departure time of the ith bus. You are also given a 0-indexed integer array passengers of length m, where passengers[j] represents the arrival time of the jth passenger. All bus departure times are unique. All passenger arrival times are unique.
You are given an integer capacity, which represents the maximum number of passengers that can get on each bus.
When a passenger arrives, they will wait in line for the next available bus. You can get on a bus that departs at x minutes if you arrive at y minutes where y <= x, and the bus is not full. Passengers with the earliest arrival times get on the bus first.
More formally when a bus arrives, either:
-
If
capacityor fewer passengers are waiting for a bus, they will all get on the bus, or -
The
capacitypassengers with the earliest arrival times will get on the bus.
Return the latest time you may arrive at the bus station to catch a bus. You cannot arrive at the same time as another passenger.
**Note: **The arrays buses and passengers are not necessarily sorted.
Example 1:
Input: buses = [10,20], passengers = [2,17,18,19], capacity = 2
Output: 16
Explanation: Suppose you arrive at time 16.
At time 10, the first bus departs with the 0th passenger.
At time 20, the second bus departs with you and the 1st passenger.
Note that you may not arrive at the same time as another passenger, which is why you must arrive before the 1st passenger to catch the bus.
Example 2:
Input: buses = [20,30,10], passengers = [19,13,26,4,25,11,21], capacity = 2
Output: 20
Explanation: Suppose you arrive at time 20.
At time 10, the first bus departs with the 3rd passenger.
At time 20, the second bus departs with the 5th and 1st passengers.
At time 30, the third bus departs with the 0th passenger and you.
Notice if you had arrived any later, then the 6th passenger would have taken your seat on the third bus.
Constraints:
-
n == buses.length -
m == passengers.length -
1 <= n, m, capacity <= 105 -
2 <= buses[i], passengers[i] <= 109 -
Each element in
busesis unique. -
Each element in
passengersis unique.
Solution (Java, C++, Python)
-
class Solution { public int latestTimeCatchTheBus(int[] buses, int[] passengers, int capacity) { // sort arrays and move in arrays from left to right and find capacity in last bus // if capcity is full in last bus then find time last passenger might have boarded then go // backward till find a slot to replace last passenger // if capacity is not full in last bus then start with last bus departure time and check if // can board on last moment and go backward till find a available time slot Arrays.sort(buses); Arrays.sort(passengers); int blen = buses.length; int plen = passengers.length; int b = 0; int p = 0; int c = 0; // find capacity in last bus while (b < blen && p < plen) { if (passengers[p] <= buses[b] && c < capacity) { c++; p++; } if (c == capacity || (p < plen && passengers[p] > buses[b])) { if (b < (blen - 1)) { c = 0; } b++; } } int start = 0; if (c == capacity) { // capcity is full in last bus, find time last passenger might have boarded start = Math.min(passengers[p - 1], buses[blen - 1]); } else { // capacity is not full in last bus, start with last bus departure time and check if can // board on last moment start = buses[blen - 1]; } // go backward till find a slot while (p > 0 && start == passengers[p - 1]) { start--; p--; } return start; } } ############ 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: 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 ############ # 2332. The Latest Time to Catch a Bus # https://leetcode.com/problems/the-latest-time-to-catch-a-bus/ class Solution: def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int: buses.sort() passengers.sort() pq = deque(passengers) P = set(passengers) res = -inf if pq[0] - 1 <= buses[0]: res = pq[0] - 1 for time in buses: cap = 0 while pq and pq[0] <= time and cap < capacity: t = pq.popleft() if t - 1 not in P and t - 1 <= time: res = max(res, t - 1) if cap + 1 != capacity and t + 1 not in P and t + 1 <= time: res = max(res, t + 1) cap += 1 if cap < capacity and time not in P: res = max(res, time) return res -
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 }
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).