Understanding the Problem
We are given:
- A set of houses positioned along a 1D straight road.
- A set of sprinklers, each with a fixed coverage radius ( r ).
- A sprinkler at position ( s ) can cover the range [s - r, s + r].
Our task is to find the minimum coverage radius ( r ) such that all houses are covered by at least one sprinkler.
Key Observations
-
Sorting Matters
- Since the problem involves searching for nearest sprinklers, sorting both houses and sprinklers simplifies the search process.
-
Binary Search on Answer
- The radius ( r ) can range from 0 (sprinklers must be at the same positions as houses) to a large number (a worst-case scenario where a single sprinkler covers all houses).
- Instead of iterating through all possible values of ( r ), we can use binary search to efficiently determine the smallest sufficient radius.
-
Checking if a Radius is Sufficient
- Given a radius ( r ), we need to verify whether all houses fall within at least one sprinkler’s coverage.
- We use binary search (
lower_bound
andupper_bound
) to efficiently determine the range covered by each sprinkler. - We maintain an extinguished array to efficiently check coverage using a sweep-line technique.
Approach
1. Sorting Houses and Sprinklers
- Sorting allows for efficient range lookups using binary search (
lower_bound
andupper_bound
). - Sorting both arrays ensures that we can efficiently determine coverage.
2. Checking if a Given Radius ( r ) is Valid
To check if a given ( r ) covers all houses:
- Use
lower_bound
andupper_bound
to find the range of houses covered by each sprinkler. - Maintain a
extinguished
array (difference array technique) to mark the start and end of coverage efficiently. - Sweep through the
extinguished
array to determine if all houses are covered.
3. Binary Search on the Minimum Radius
-
Set search space:
low = 0
(minimum possible radius).high = 10^9
(large upper bound).
-
Perform Binary Search:
- Check if mid radius is sufficient using
check()
. - If sufficient, try reducing the radius (
high = mid - 1
). - If not sufficient, increase the radius (
low = mid + 1
). - The smallest valid ( r ) found is the answer.
- Check if mid radius is sufficient using
Complexity Analysis
-
Sorting Houses and Sprinklers
- O(N log N) + O(M log M)
-
Checking a Single Radius ( r )
- Each sprinkler uses O(log N) binary search operations.
- We iterate over sprinklers, so total complexity is O(M log N).
-
Binary Search on ( r )
- Runs in O(log (max_radius)) = O(log 10^9) which is approx O(30)
Final Complexity
O(N log N) + O(M log M) + O(M log N log 10^9)