Minimum Patrol Guards
Hard · rating 1800 · Greedy, Intervals
Sensors sit at integer positions along a fence. Each guard covers a closed segment of length L (from any real start point). The first line has n and L. The second line has the n sensor positions. Print the fewest guards needed so every sensor is covered.
Constraints: 1 ≤ n ≤ 105, 0 ≤ L ≤ 109
Editorial
Approach
Sort the sensor positions. Sweep left to right: the leftmost uncovered sensor forces a guard, and greedily that guard should reach as far right as possible — covering [p, p+L]. Skip every sensor within reach, then repeat.
Why greedy is optimal
Some guard must cover the leftmost sensor; starting that guard exactly at the sensor covers the most to its right, so no other placement can do better.
guards = 0; i = 0
while i < n:
guards += 1; end = pos[i] + L
while i < n and pos[i] <= end: i += 1Complexity
Time: O(n log n). Space: O(1).
Related problems
- Coin Change — Hard
- Job Sequencing — Hard
- Gas Station — Medium
- Minimum Meeting Rooms — Hard
- Partition Labels — Medium
- Merge Intervals — Medium