Last Updated: 21 Nov, 2021

Highway BillBoards

Moderate

Asked in companies

Solve now

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.

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.

Solve now

Approaches

01 Approach

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]

Solve now