Last Updated: 3 Sep, 2021
Light Up the Street!
Moderate
Asked in company
You are walking on a street of length ‘N’. You want to light up the street by installing street lights.
There are 'M' streetlights and the 'ith' streetlight can be installed at position 'Ci'.
You are also given the range of the streetlights 'R' which means that the 'ith' streetlight installed at position 'Ci' will enlighten street from 'Ci-R' to 'Ci+R'.
Output the minimum number of street lights required to light up the whole street or output -1 if it is impossible to light the whole street under the given conditions.
It is sufficient to enlighten the integer positions, it is not required to enlighten the area between two integer positions.
For example : 'N' = 8, 'M' = 2, 'C' = [1, 6], 'R' = 2. The answer for this case is 2 as we can enlighten streetlight at position 1 and streetlight at position 6. These two will enlighten the positions 1, 2, 3, 4, 5, 6, 7, 8.
Example:-
N=10, M=3
C = [2,4,7] ( The positions of the streetlights )
R = 3 ( The range of the street-lights)
The answer will be 2 as we can install the first street light at position 2 so it illuminates the street from positions from 1 to 5 and the third street light at 7 so it illuminates the street from positions from 4 to 10.
Input Format :
The first line contains a single integer ‘T’ representing the number of test cases. Then each test case follows.
The first line of each test case contains two integers ‘N’ and ‘M’ denoting the length of the street and the number of street lights that are provided to you.
The next line of every test case contains ‘M’ integers ('C[i]') which denote the position of the 'ith' streetlight.
The next line of every test case contains an integer 'R' which denote the range of the street lights.
Output Format :
For each test case, return the minimum number of street lights required to light up the street. If it is not possible to light up the whole street, return -1.
The output of each test case should be printed in a separate line.
Note :
You are not required to print anything, it has already been taken care of. Just implement the function.
Constraints :
1 <= T <= 10
1 <= N <= 10^9
1 <= M <= 10^5
1 <= C[i] <= N
0 <= R <= 10^9
It is guaranteed that the sum of ‘M’ over all test cases is less than equal to 10^5.
Time Limit: 1 sec
Approaches
Approach:
We will try to generate all possible combinations of Lights
which are turned On Recursively and choose the Combination with a minimum number of lights which covers the whole street.
Algorithm:
- Make current range 0 , and call your recursive function.
- Now for each Checkpoint, you will now have the last point of the last lighted up range.
- If the last range point cannot cover Checkpoint[i] - K, return a very high value which represents that we cannot reach.
- Else you either skip the current Checkpoint. Therefore the last point remains unchanged and stores the returning value in the answer variable.
- Or select current element update last covering point as Checkpoint[i] + K, and update the answer to a minimum of the previous value of answer or 1 + value of recursive function after selecting Checkpoint.
- After reaching the current index to M, we need to return 0 if we have crossed N or a big value that we were not able to cover the total N length of the street.
- Return answer
Approach :
- Let us consider the Street as a number line; We need to light up all the points of the number lines from 1 - ‘N’ of this number line.
- So we can Consider all the points till 0 are already light up.
- Now, as we have sorted ‘CHECKPOINTS’, we can greedily decide when to Light Up the Checkpoint.
- We will start iterating over all ‘CHECKPOINTS’ and keep three variables to stores ‘LAST_RANGE’ and ‘MAXIMUM_RANGE_TILL_NOW’
- For each ‘CHECKPOINTS,’ we check if ‘CHECKPOINT’s’ range overlaps with ‘LAST_RANGE.’
- If Our current ‘CHECKPOINT’ does not overlap with our ‘LAST RANGE.’ We Check the same for our ‘MAXIMUM_RANGE_TILL_NOW.’
- Suppose our current ‘CHECKPOINT’ fails to Overlap with both Ranges. Our Answer is -1 Since we were unable to cover non-light-up Points.
- Else, we increment our Answer by one and Update our ‘LAST RANGE’ to ‘MAXIMUM_RANGE_TILL_NOW,’ assuming it as the last Checkpoints range we turned On to cover the non-light-up points on the Number line.
- We Update our ‘MAXIMUM_RANGE_TILL_NOW’ as Position of Current ‘CHECKPOINT’ + ‘K.’
- After Iterating all the ‘CHECKPOINTS,’ we will check if our ‘LAST RANGE’ already covers till ‘N.’
- If Not, We will Check if our ‘MAXIMUM_RANGE_TILL_NOW’ can cover till ‘N’ point.
- If ‘MAXIMUM_RANGE_TILL_NOW’ fails to cover till ‘N’, set Answer as -1.
- Else Increment the value of Answer by 1.
- If Not, We will Check if our ‘MAXIMUM_RANGE_TILL_NOW’ can cover till ‘N’ point.
- Return Answer
Algorithm :
- Initialize Three Variables ‘LAST_RANGE’, ‘MAX_RANGE,’ and ‘ANS’ as 0.
- Start Iterating overall ‘CHECKPOINTS.’
- If Our Current ‘CHECKPOINTS’ range [CHECKPOINT[i] - K, CHECKPOINT[i] + K], do not overlap with our ‘LAST RANGE’.
- We will Check overlaps With Between the Current ‘CHECKPOINTS’ range [CHECKPOINT[i] - K, CHECKPOINT[i] + K] and ‘MAX_RANGE.’
- If ‘MAX_RANGE’ overlaps with the ‘CHECKPOINTS[i]’ range, increment the ‘ANS’ value by 1. Update ‘LAST_RANGE’ with the value of ‘MAX_RANGE’
- Else Return -1.
- We will Check overlaps With Between the Current ‘CHECKPOINTS’ range [CHECKPOINT[i] - K, CHECKPOINT[i] + K] and ‘MAX_RANGE.’
- If Our Current ‘CHECKPOINTS’ range [CHECKPOINT[i] - K, CHECKPOINT[i] + K], do not overlap with our ‘LAST RANGE’.
- Update ‘MAX_RANGE’ = ‘CHECKPOINT[i]’ + ‘K’.
- After Iterating over all the ‘CHECKPOINTS,’ Check If ‘LAST_RANGE’ covers till ‘N’
- If ‘LAST_RANGE’ is less than ‘N’
- We check if ‘MAX_RANGE’ covers ‘N,’ If ‘MAX_RANGE’ fails to do so, we return -1.
- Else we Increment ‘ANS’ value by 1.
- If ‘LAST_RANGE’ is less than ‘N’
Return ‘ANS’