Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
import java.util.Arrays;
public class HighwayBillboard {
public int maxRevenue(int[] billboard, int[] revenue, int distance, int milesRes) {
int[] MR = new int[distance + 1];
//Next billboard which can be used will start from index 0 in billboard[]
int nextBillBoard = 0;
//example if milesRes = 5 miles then any 2 bill boards has to be more than
//5 miles away so actually we can put at 6th mile so we can add one mile milesRes
milesRes = milesRes + 1; // actual minimum distance can be between 2 billboards
MR[0] = 0;
for (int i = 1; i <= distance; i++) {
//check if all the billboards are not already placed
if(nextBillBoard < billboard.length){
//check if we have billboard for that particular mile
//if not then copy the optimal solution from i-1th mile
if (billboard[nextBillBoard] != i) {
//we do not have billboard for this particular mile
MR[i] = MR[i - 1];
} else {
//we do have billboard for this particular mile
//now we have 2 options, either place the billboard or ignore it
//we will choose the optimal solution
if(i>=milesRes){
MR[i] = Math.max(MR[i - milesRes] + revenue[nextBillBoard], MR[i - 1]);
}else{
//there are no billboard placed prior to ith mile
//we will just place the billboard
MR[i] = revenue[nextBillBoard];
}
nextBillBoard++;
}
}else{
//All the billboards are already placed
//for rest of the distance copy the previous optimal solution
MR[i] = MR[i - 1];
}
}
//System.out.println(Arrays.toString(MR));
return MR[distance];
}
public static void main(String[] args) {
int[] x = {6, 7, 12, 13, 14};
int[] revenue = {5, 6, 5, 3, 1};
int distance = 20;
int milesRestriction = 5;
HighwayBillboard h = new HighwayBillboard();
int result = h.maxRevenue(x, revenue, distance, milesRestriction);
System.out.println("Maximum revenue can be generated :" + result);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment