Problem Brief

Minimum Cars for Rental Requests

FULLTIMEONSITE INTERVIEW

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:

Returns

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

1Example 1

Input

requests = [[1, 3], [2, 4], [4, 6]]

Output

["0: (1,3) (4,6)", "1: (2,4)"]

Explanation

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.

Input

requests = [[1, 2], [2, 3], [3, 4], [4, 5]]

Output

["0: (1,2) (2,3) (3,4) (4,5)"]

Explanation

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

Limits and guarantees your solution can rely on.