Highway BillBoards

Moderate
0/80
profile
Contributed by
13 upvotes
Asked in companies
Expedia GroupBrowserStackFlipkart limited

Problem statement

You have to place ‘N’ billboards across a highway of ‘M’ kilometres. All the possible sites to place a billboard is given in the ‘billboards’ array. The revenue earned by placing a billboard is described by the ‘revenue’ array, billboard at ‘billboard[i]’ will earn the revenue equal to ‘revenue[i]’. There is a condition that no two billboards can be placed within ‘X’ kilometres of each other.

For Example : 
You are given billboards = [2, 8, 9, 10, 15], revenue = [20, 50, 10, 30, 5], ‘M’ = ‘20’, ‘X’ = 5, here we can place the billboard at positions 2, 8, 15, which will give the profit as 20 + 50 + 5 = 75. Hence the answer is 75.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains a single integer ‘T’, representing the number of test cases.

The first line of each test case contains 3 space-separated integers ‘M’, ‘N’ and ‘X’, where ‘N’ is the number of billboards positions available, ‘M’ is the length of the highway, and ‘X’ is the minimum distance allowed between two billboards, respectively.

The second line of input contains ‘N’ space-separated integers, describing the ‘billboards’ array.

The third line of input contains the ‘N’ space-separated integers, describing the ‘revenue’ array.
Output Format: 
For each test case, print a single integer representing the maximum profit earned.

Print a separate line for each test case.
Constraints: 
1 <= T <= 10
1 <= X <= M
1 <= billboards[i] <= M
1 <= |revenue[i]| <= 10^9

Time Limit: 1 sec.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the function.
Sample Input 1:
2
20 5 5
2 8 9 10 15
20 50 10 30 5
8 3 3
1 3 5
5 8 10
Sample Output 1:
75
15
Explanation:
For the first test case, billboards = [2, 8, 9, 10, 15], revenue = [20, 50, 10, 30, 5], ‘M’ = ‘20’, ‘X’ = 5, here we can place the billboard at positions 2, 8, 15, which will give the profit as 20 + 50 + 5 = 75. Hence the answer is 75.

For the second test case, billboards = [1, 3, 5], revenue = [5, 8, 10], ‘M’ = ‘8, ‘X’ = 3, here we can place the billboard at positions 1 and 5, which will give the profit as 5  + 10 = 15. Hence the answer is 15.
Sample Input 2:
2
18 5 1
1 2 3 6 14
36 61 66 31 36
17 6 2
1 2 3 6 10 12
25 19 67 18 56 18
Sample Output 2:
169
141
Hint

Try to iterate over the highway and calculate the answer for each position accordingly.

Approaches (1)
Implementation

In this approach, we will iterate through 1 to ‘M’ and for each kilometre, we can check the maximum profit earned. If the current position is present in the ‘billboards’ array, we will have to check if it’s optimal to add a billboard there or not, and if we place a billboard at position ‘i’ we will have to ignore the billboard ‘X’ miles.

If we place the billboard, we will have to add the revenue of the current billboard and maximum revenue of ‘current position - X’ positions.

 

Algorithm:

  • Initialise an empty array of size M + 1,’maxRevenue’
  • Set ‘nextIndex’ as 0
  • Iterate currPos from 1 to M
    • If ‘nextIndex’ is greater than the length of the billboards array
      • Set maxRevenue[currPos] as maxRevenue[currPos - 1]
      • Continue the loop
    • If billboards[nextIndex] is not equal to currPos
      • Set maxRevenue[currPos] = maxRevenue[currPos - 1]
      • Continue the loop
    • If currPos is less than equal to ‘x’
      • Set maxRevenue as the maximum of maxRevenue[currPos - 1] and revenue[nextIndex]
    • Otherwise,
      • Set maxRevenue as the maximum of maxRevnue[currPos - 1] and maxRevenue[currPos - x - 1] + revenue[nextIndex]
  • Return maxRevenue[m]
Time Complexity

O(M), Where M is the length of the highway.

 

We are iterating from 1 to M on all positions of the highway, all other operations are constant-time operations. Hence the final time complexity is O(M).

Space Complexity

O(M), Where M is the length of the highway.

 

We are maintaining an array of length M, in the algorithm. Hence the final space complexity is O(M).

Code Solution
(100% EXP penalty)
Highway BillBoards
Full screen
Console