Museum Access Slot Trimming
Remaining fragments after removing one interval from disjoint intervals
A museum has scheduled access slots for a conservation gallery. A security inspection makes the gallery unavailable during one blackout interval.
Each entry [start, end] in slots represents the half-open interval [start, end): access begins at start and ends just before end. The slots are sorted by start time and do not overlap, although consecutive slots may touch. blackout is another half-open interval [blocked_start, blocked_end).
Remove every portion of every slot that lies inside the blackout. A slot may disappear, remain unchanged, become shorter, or split into two fragments.
Return all remaining nonempty fragments as [start, end] pairs in increasing start-time order. Preserve original slot boundaries: never combine fragments from different slots, even when they touch. Touching the blackout at an endpoint does not remove any time.
Times are integer offsets from the museum's reference time and may be negative.
Examples
Example 1
Input: slots = [[0,5],[7,12],[15,18]], blackout = [3,9] Output: [[0,3],[9,12],[15,18]]
The blackout removes the end of the first slot and the beginning of the second slot. The third slot is unaffected.
Example 2
Input: slots = [[-4,10]], blackout = [0,6] Output: [[-4,0],[6,10]]
The blackout lies strictly inside the only slot, so that slot leaves two separate fragments.
Example 3
Input: slots = [[1,4],[4,7]], blackout = [7,9] Output: [[1,4],[4,7]]
The blackout begins exactly when the last slot ends. Neither slot loses any time, and their shared boundary must remain in the returned list.
Constraints
- 0 <= slots.length <= 3000
- Each slot and blackout contains exactly two integers.
- -10^9 <= every endpoint <= 10^9
- Every interval has start < end.
- For every valid i, slots[i][1] <= slots[i + 1][0].
The intended solution takes O(n) time and O(1) auxiliary space excluding the returned fragments, where n is the number of slots. Half-open endpoint rules and preservation of original boundaries are important.
Hints
Show hint 1Hint 1
Consider the portion of each slot before the blackout and the portion after it separately.
Show hint 2Hint 2
A candidate fragment should be returned only if its start is strictly less than its end.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you handle several sorted, nonoverlapping blackout intervals in linear time?
- How would the result change if touching fragments from different original slots had to be combined?
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