Assign the Minimum Number of Cars to Rental Requests

Each rental request has a unique request ID, a start time, and an end time. Assign a car ID to every request so that one car is never used by overlapping rentals, and return the minimum number of cars required along with a valid assignment. ### Constraints and Clarifications Clarify whether a car ending a rental at time t can begin another at t. For this practice solution, use half-open intervals [start,end) with start<end, so immediate reuse is allowed. These endpoint and nonzero-duration choices are not specified in the report. No size bounds are supplied. Preserve request IDs when returning assignments. Car IDs are labels; several different minimum-car assignments can be valid, and no unique labeling or partition is required. ### What a Strong Answer Covers Sort requests, reuse the earliest available car with a min-heap, retain the assignment, and prove that every newly allocated car is necessary. Explain how the endpoint convention changes the reuse comparison. ### Follow-up Questions - What changes if touching intervals are considered overlapping? - Why does sorting by request ID not generally support the greedy argument?