218. Minimum Cabs With Wait Period for Scheduled Bookings

Minimum Cabs With Wait Period for Scheduled Bookings

You are given a list of scheduled cab bookings. Each booking has a start time and an end time. A cab can handle multiple bookings, but after completing one booking it must wait for a fixed wait period before starting another booking.

Find the minimum number of cabs required to complete all bookings.

As a follow-up, given a fixed number of available cabs, minimize the maximum number of rides assigned to any one cab while still completing all bookings.

Method Signatures

Minimum Cabs Required

int minCabsRequired(List<String> bookings, int waitPeriod)

bookings: each string is in the format "start,end".
start and end are integer times in minutes.
A cab can take booking b after booking a only if endA + waitPeriod ≤ startB.
Return the minimum number of cabs needed to complete all bookings.

Minimize Maximum Rides Per Cab

int minimizeMaxRidesPerCab(List<String> bookings, int cabCount, int waitPeriod)

bookings: each string is in the format "start,end".
cabCount: number of available cabs.
waitPeriod: required waiting time after each ride.
Return the smallest possible value of the maximum rides assigned to any one cab.
If it is not possible to complete all bookings using at most cabCount cabs, return -1.
For each cab, its assigned bookings must be ordered so that every next booking starts only after the previous booking ends plus the wait period.
Cabs with zero rides are allowed and do not affect the maximum ride count.

Booking Rules

The input bookings may be in any order.
Each booking must be assigned to exactly one cab.
One cab cannot handle overlapping bookings.
The wait period is applied after every completed booking before the same cab can start another booking.
If two bookings have the same start and end time, they are treated as separate bookings.

Constraints

1 ≤ bookings.size() ≤ 100,000
0 ≤ start < end ≤ 1,000,000,000
0 ≤ waitPeriod ≤ 1,000,000,000
1 ≤ cabCount ≤ 100,000
Each booking string contains exactly two integers separated by a comma.

Examples

Example 1

minCabsRequired(bookings = List.of("0,30", "10,20", "35,50"), waitPeriod = 5)

Output: 2

Explanation: One cab can handle "0,30" and then "35,50" because 30 + 5 ≤ 35. The booking "10,20" overlaps with "0,30", so a second cab is needed.

Example 2

minCabsRequired(bookings = List.of("5,15", "15,25", "25,35"), waitPeriod = 1)

Output: 2

Explanation: The same cab cannot take "5,15" followed immediately by "15,25" because it must wait for 1 minute. Therefore, at least two cabs are required.

Example 3

minimizeMaxRidesPerCab(bookings = List.of("0,10", "5,15", "12,20", "25,30"), cabCount = 2, waitPeriod = 2)

Output: 2

Explanation: One valid assignment is cab 1 taking "0,10" and "12,20", and cab 2 taking "5,15" and "25,30". Both cabs follow the wait-period rule, so the maximum rides assigned to any cab is 2.

Example 4

minimizeMaxRidesPerCab(bookings = List.of("0,100", "10,90", "20,80"), cabCount = 2, waitPeriod = 5)

Output: -1

Explanation: All three bookings overlap, so three cabs are required. With only two cabs, completing all bookings is impossible.

Example 5

minimizeMaxRidesPerCab(bookings = List.of("0,10", "12,20", "22,30", "40,50", "45,55"), cabCount = 3, waitPeriod = 2)

Output: 2

Explanation: There are 5 bookings and 3 cabs, so the answer cannot be less than ceil(5 / 3) = 2. One valid assignment is cab 1 taking "0,10" and "12,20", cab 2 taking "22,30" and "40,50", and cab 3 taking "45,55". Therefore, the smallest possible maximum is 2.