Wildlife Capture Commitments
Minimum number of integer points meeting each interval's required count
A wildlife survey uses synchronized cameras. Whenever the cameras are triggered at an integer timestamp, they produce one survey snapshot. A timestamp can be used at most once, and the same snapshot can satisfy several survey commitments.
You are given windows, where each entry [start, end, required] means that at least required distinct snapshot timestamps must lie in the inclusive interval [start, end].
Choose a set of integer timestamps that satisfies every commitment. Return the minimum possible number of timestamps in that set.
Timestamps may be negative: they are offsets from the survey's reference time. You do not need to return the timestamps themselves. If there are no commitments, return 0.
Examples
Example 1
Input: windows = [[1,4,2],[3,6,3],[5,7,2]] Output: 4
For the three commitments, snapshots at timestamps 3, 4, 5, and 6 satisfy every requirement. Three snapshots cannot suffice: the middle window would need all three, while the first and last windows would each need two, but their intersection is empty.
Example 2
Input: windows = [[-3,2,2],[-1,0,2]] Output: 2
The narrow window requires both timestamps -1 and 0. Those same snapshots also satisfy the wider window, so no additional timestamps are needed.
Example 3
Input: windows = [[0,1000000000,1000000001]] Output: 1000000001
The window contains exactly 1,000,000,001 integer timestamps and requires that many snapshots. Every timestamp in the window must be selected.
Constraints
- 0 <= windows.length <= 2500
- Each entry in windows has exactly three integers: [start, end, required].
- -10^9 <= start <= end <= 10^9
- 0 <= required <= end - start + 1
The intended solution runs in O(n log n) time and O(n) space, where n is the number of commitments. Timestamp ranges must never be expanded into individual points. The brute implementation deliberately uses a direct interval-list simulation, so even a single enormous window is handled without excessive memory or iteration.
Hints
Show hint 1Hint 1
Process commitments in increasing order of their right endpoint. If one still needs snapshots, selecting the latest available timestamps preserves the most opportunities for later commitments.
Show hint 2Hint 2
Represent selected timestamps as disjoint inclusive intervals rather than individual points. Previously selected suffix intervals can be absorbed into a newly selected interval, while cumulative interval lengths support coverage queries.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you also return a compact representation of an optimal timestamp set as disjoint inclusive intervals?
- What changes if snapshots can only be taken at timestamps from a supplied sorted list of permitted 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