Last Updated: 20 Apr, 2021
Traffic Lights
Moderate
Asked in company
There is a street of length X with positions numbered from 0 to X (0,1,…, ’X’). Initially, there are no traffic lights in these slots. Later ‘N’ sets of traffic lights are added to the street one after another. The ‘POS’ array tells the position of the ‘i’th light.
Your task is to calculate the length of the longest passage without traffic lights after each addition.
For example:
Given:- ‘X’ = 5 and ‘N’ = 2.
‘POS’[] = 3, 4
The output will be 3 and 3.
Initially, there are no lights, and we install a light at position three; therefore, there is a segment between the 3 and 6.
Then we install a light at position four; therefore, the largest gap becomes between 0 to 3.
Input format :
The first line of input contains an integer ‘T’ denoting the number of test cases.
The first line of each test case contains two space-separated integers, 'X' and ‘N’, where ‘X’ is the length of the road and ‘N’ is the number of lights.
The next line contains ‘N’ space-separated integers denoting the position of the ith light.
Output format :
For each test case, print a single line containing a single integer denoting the maximum gap for every light we install.
The output of each test case will be printed in a separate line.
Note:
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 2000
1 <= X <= 10 ^ 8
1 <= POS[i] <= X
Where ‘T’ is the total number of test cases, ‘N’ is the number of lights we install, ‘X’ is the length of the road, and ‘POS[i]’ denotes the position of the 'i th' light.
Time limit: 1 sec.
Approaches
The main idea is to use a set ‘LIGHTS’ and a multiset ‘DISTANCE’ to maintain the position of light and distance maintains all the distances. For a given position, find the next position of the light and the previous position of the light, and put it into the ‘DISTANCE’ set, and the end of the set contains the answer since the values are always sorted in increasing order.
- Maintain a set ‘LIGHTS’ and multiset ‘DISTANCE’.
- Push 0 and ‘X’ in the ‘LIGHT’ to mark polls.
- For every position in the ‘POS’ array :
- Find ‘GREATER_POS’, which is the upper_bound of the current position from ‘LIGHTS.’
- Find ‘SMALLER_POS’, which is the previous position of the ‘GREATER_POS’.
- The answer is maximum value till now, which is the last position of the ‘DISTANCE’ set.
- Maintain a vector ‘RES’, which contains the max gap till the ith position.
- Return ‘RES’ as the final answer.
The main idea is to maintain an array of sorted points and then, for each query, find the lower bounded value from the actual array of points.
- Maintain an array ‘SORTEDPOINTS’ of size ‘N’ + 2, where ‘N’ is the size of ‘POS’ array and a ‘POINTS’ array which is the same as ‘POS’ but with 1-based indexing.
- We use a helper function ‘calculateTrafficLights’ which takes :
- ‘N’
- ‘POINTS’
- ‘SORTED_POINTS’
- In the function :
- Maintain three arrays ‘RIGHT’, ‘LEFT’ and ‘PASSAGES.’
- A variable ‘MAX_LENGTH’ stores the max consecutive distance between two points.
- Loop from N to 1 :
- ‘PASSAGES’[i] = ‘MAXLENGTH’
- Now update the ‘MAXLENGTH’ by finding the position ‘POS’ of the current point using lower_bound
- ‘MAX_LENGTH’ = max(‘SORTED_POINTS’[‘RIGHT’[‘POS’]] - ‘SORTED_POINTS’[‘LEFT’[‘POS’]], MAX_LENGTH)
- Maintain an array ‘ARR’ and store all values from 1 to ‘N’ in ARR.
- Return ‘ARR’ as a result.
Similar problems