Festival Calibration Moments
Lexicographically largest shortest integer list hitting all intervals
A film festival broadcasts a short audio calibration tone to all screening rooms at selected integer times. Each room has one acceptable time window for receiving a tone.
You are given windows, where windows[i] = [start, end] means room i must receive at least one tone at a time t satisfying start <= t <= end. Both endpoints are included. One broadcast can satisfy any number of rooms whose windows contain its time.
Return a strictly increasing list of broadcast times that satisfies every room using the fewest possible broadcasts.
If several minimum-size lists are possible, return the lexicographically largest one: at the first position where two lists differ, prefer the list with the larger time.
If there are no rooms, return an empty list.
Examples
Example 1
Input: windows = [[1,4],[2,6],[7,9]] Output: [4,9]
The first two rooms have overlapping acceptable windows, so they can share a broadcast. The third room needs a separate broadcast. The tie-breaking rule places each broadcast as late as possible without increasing the number needed.
Example 2
Input: windows = [[2,5],[5,8],[0,10]] Output: [5]
Every window contains the shared endpoint of the first two windows. Because endpoints are included, one broadcast can satisfy all rooms.
Example 3
Input: windows = [] Output: []
There are no rooms to calibrate, so no broadcasts are needed.
Constraints
- 0 <= windows.length <= 4000
- Each element of windows contains exactly two integers.
- 0 <= start <= end <= 1000000000
- Windows may be unsorted, identical, nested, or reduced to a single time.
The intended solution takes O(n log n) time and O(n) auxiliary space. The lexicographic tie-break applies only among schedules with the minimum number of broadcasts.
Hints
Show hint 1Hint 1
Consider the room whose acceptable window ends first. How late can a broadcast satisfying that room occur?
Show hint 2Hint 2
After choosing that time, remove every window containing it and repeat the same decision.
Follow-up questions
What an interviewer might ask once you have a working solution.
- Explain why moving the first broadcast to the earliest window end cannot increase the number of broadcasts needed.
- How would the implementation change if the windows were already sorted by their ending times?
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