Light Up the Street!

Moderate
0/80
Average time to solve is 10m
profile
Contributed by
24 upvotes
Asked in company
Microsoft

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
10 4
2 4 6 8
3
2 3
1 1 1
3
1
0
Sample Output 1 :
2
1
Explanation for Sample Output 1 :
In the first test case, the answer is 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 8 so it illuminates the street from positions from 5 to 10.

In the second test case, we can install a single street light at checkpoint 1 so it illuminates position 1, so the number of street lights required is 1.
Sample Input 2 :
1
5 1
1 
1
Sample Output 2 :
-1
Hint

What is the maximum range a particular Checkpoint can cover?

Approaches (2)
Brute Force

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
Time Complexity

O(2^M), where ‘M’ is the number of Checkpoints.

We either select the current Checkpoint or not which results in total of 2^M possibilities.

Space Complexity

O(M), size of the recursive stack in the worst case.

Code Solution
(100% EXP penalty)
Light Up the Street!
Full screen
Console