Fewest Probes to Touch Every Window
A monitoring job must sample every maintenance window at least once. Window i is the closed interval windows[i] = [start, end]. One probe fired at integer time t samples every window with start <= t <= end.
Return the minimum number of probes needed so that every window is sampled.
Example 1
Input: windows = [[1,4],[2,5],[7,9],[8,10],[3,3]] Output: 2 Explanation: A probe at 3 hits the first three windows sorted by end; a probe at 9 hits the rest.
Example 2
Input: windows = [[1,2],[3,4],[5,6]] Output: 3 Explanation: No two windows share a time.
Constraints
- 0 <= windows.length <= 2 * 10^4
- -10^5 <= start <= end <= 2 * 10^5
Hint 1
Sort the windows by their end time.
Hint 2
Fire a probe at the end of the first window not yet sampled; it is the latest moment that still hits it, so it covers as much as possible.
Discussion 0
Join free to post in the discussion.
Good practice for: Backend Developer, Site Reliability Engineer, Data Engineer, Automation Test Engineer, Embedded Systems Engineer
Run checks your code on 3 sample tests. Submit runs all 8 tests, including hidden ones, and earns points. Use console.log to debug. Python's first run can take a few seconds while it starts.