FastPrep
Problem · Intervals

Minimum Cars for Rental Requests

● MediumGoogleFULLTIMEONSITE INTERVIEW
See Google hiring insights

You are given rental requests, where each request is represented as [pickupTime, returnTime].

A single car cannot serve overlapping requests. If one request ends exactly when another begins, the same car may serve both.

Return one deterministic minimum-car assignment using the following canonical rules:

  • Process requests in ascending order of pickupTime, breaking ties by returnTime.
  • When multiple cars are available, reuse the available car with the smallest car id.
  • When no existing car is available, create a new car with the next unused id starting from 0.

Each returned string must use the format "carId: (p1,r1) (p2,r2) ...". The number of returned lines is the minimum number of cars needed.

Function Description

Complete the function assignMinimumCars in the editor below.

assignMinimumCars has the following parameter:

  1. int[][] requests: rental intervals [pickupTime, returnTime]

Returns

String[]: the deterministic assignment lines in ascending car id order.

Examples
01 · Example 1
requests = [[1, 3], [2, 4], [4, 6]]
return = ["0: (1,3) (4,6)", "1: (2,4)"]

Two cars are necessary because the first two requests overlap. Car 0 becomes available at time 3 and can serve the request starting at time 4.

02 · Example 2
requests = [[1, 2], [2, 3], [3, 4], [4, 5]]
return = ["0: (1,2) (2,3) (3,4) (4,5)"]

Each request starts exactly when the previous one ends, so one car can serve all of them.

Constraints
  • 1 <= requests.length <= 2 * 10^5
  • 0 <= pickupTime < returnTime <= 10^9
  • The returned assignment must follow the deterministic rules stated above.
More Google problems
drafts saved locally
public String[] assignMinimumCars(int[][] requests) {
    // write your code here
}
requests[[1, 3], [2, 4], [4, 6]]
expected["0: (1", "3) (4", "6)", "1: (2", "4)"]
sign in to submit