Ward Monitor Reservation Cuts
Minimum intervals to remove so overlap never exceeds a given capacity
A hospital ward has capacity portable monitors. Each planned patient observation reserves one monitor for a time interval.
You are given reservations, where reservations[i] = [start, end] represents a reservation active during the half-open interval [start, end). A reservation ending at a time does not overlap a reservation starting at that same time. Negative times represent moments before the ward's reference time.
A reservation can either be kept in full or canceled in full. Kept reservations must never require more than capacity monitors at any moment. Monitors are interchangeable, and switching a monitor between reservations takes no time.
Return the minimum number of reservations that must be canceled. Reservations with identical endpoints are still separate reservations. The input need not be sorted.
Examples
Example 1
Input: reservations = [[1,5],[2,6],[3,4]], capacity = 2 Output: 1
All three reservations are active between times 3 and 4, but only two monitors are available. Canceling any one of them is sufficient.
Example 2
Input: reservations = [[0,2],[2,4],[2,3]], capacity = 1 Output: 1
The reservation ending at time 2 can share a monitor with one starting at time 2. The only conflict is between the two reservations that start at time 2, so canceling one resolves it.
Example 3
Input: reservations = [[0,10],[0,9],[1,2],[3,4],[5,6]], capacity = 2 Output: 1
Two long reservations surround three mutually nonoverlapping short reservations. With two monitors, canceling one long reservation allows all three short reservations and the other long reservation to remain.
Constraints
- 0 <= reservations.length <= 6000
- Each reservation contains exactly two integers, start and end.
- -10^9 <= start < end <= 10^9
- 1 <= capacity <= 6000
The result is a count, so different optimal cancellation sets do not affect the answer. Intended complexity: O(n log n) time and O(n) auxiliary space.
Hints
Show hint 1Hint 1
Process reservations in increasing order of start time, removing reservations that have already ended from the active set.
Show hint 2Hint 2
If keeping a new reservation exceeds capacity, which active reservation is least useful for leaving room for future reservations?
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you also return a set of canceled original indices, using a fixed tie-breaking rule?
- If each reservation has a different cancellation cost, why might discarding the latest-ending reservation no longer be optimal?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem