Street Lights are installed at every position along a 1-D road of length n. Locations[]…
- User
Street Lights are installed at every position along a 1-D road of length n. Locations[] (an array) represents the coverage limit of these lights. The ith light has a coverage limit of locations[i] that can range from the position max((i – locations[i]), 1) to min((i + locations[i]), n ) (Closed intervals). Initially all the lights are switched off. Find the minimum number of fountains that must be switched on to cover the road.
- Assistant
To solve the problem of covering a 1-D road of length
nwith the minimum number of street lights, we can model it as an interval covering problem. Here's a step-by-step approach to achieve the solution:Step 1: Understand the Coverage of Each Street Light
Each street light
ihas a coverage range determined bylocations[i]. Specifically, the light at positionicovers from:- Left Boundary:
max(i - locations[i], 1) - Right Boundary:
min(i + locations[i], n)
This gives us an interval
[left_i, right_i]for each street light.Step 2: Collect All Coverage Intervals
For each street light, calculate its coverage interval and store all these intervals.
Step 3: Sort the Intervals
Sort the intervals based on their starting points (
left_i). If two intervals have the same starting point, sort them by their ending points (right_i) in descending order. This helps in selecting the interval that covers the farthest point first.Step 4: Apply a Greedy Algorithm to Select Minimal Intervals
Use a greedy approach to select the minimum number of intervals that cover the entire road from
1ton. Here's how:-
Initialize Variables:
current_end: The farthest point currently covered. Start with0.next_end: The farthest point that can be covered in the next step.count: Number of street lights turned on.index: To iterate through the sorted intervals.
-
Iterate Through the Intervals:
- While
current_endis less thann, do the following:- Find all intervals where
left_iis less than or equal tocurrent_end + 1. Among these, choose the one with the maximumright_i. - Update
current_endto this maximumright_i. - Increment
countas you've selected a new street light. - If no interval can extend the coverage (
next_endremains the same ascurrent_end), it's impossible to cover the road.
- Find all intervals where
- While
-
Termination:
- If the entire road is covered (
current_end >= n), return thecountas the minimum number of street lights needed.
- If the entire road is covered (
Step 5: Implementation
Below is a Python implementation of the above approach:
def min_street_lights(n, locations): intervals = [] for i in range(1, n + 1): left = max(i - locations[i - 1], 1) right = min(i + locations[i - 1], n) intervals.append((left, right)) # Sort intervals by start; if same start, by end descending intervals.sort(key=lambda x: (x[0], -x[1])) count = 0 current_end = 0 next_end = 0 index = 0 m = len(intervals) while current_end < n: while index < m and intervals[index][0] <= current_end + 1: next_end = max(next_end, intervals[index][1]) index += 1 if next_end == current_end: # Cannot extend coverage return -1 # or any indication that it's impossible count += 1 current_end = next_end return count # Example Usage: n = 5 locations = [1, 2, 1, 0, 1] print(min_street_lights(n, locations))Explanation of the Example:
- Input:
n = 5,locations = [1, 2, 1, 0, 1] - Coverage Intervals:
- Light 1: [1, 2]
- Light 2: [1, 4]
- Light 3: [2, 4]
- Light 4: [4, 4]
- Light 5: [4, 5]
- Greedy Selection:
- Select Light 2 covering up to position
4. - Then select Light 5 covering up to position
5.
- Select Light 2 covering up to position
- Total Lights Switched On:
2
Conclusion
By modeling the problem as an interval covering task and applying a greedy strategy, we efficiently determine the minimum number of street lights required to cover the entire road. This approach ensures optimality with a time complexity of O(n log n) due to the sorting step.
- Left Boundary: