Highway Billboard

Problem

You have a highway of length M miles and n possible billboard sites at positions x1 < x2 < ... < xn (each in [0, M]). Placing a billboard at position xi yields revenue ri. Two billboards must be strictly more than k miles apart (the original statement uses k = 5). Choose a subset of sites to maximize total revenue.

Examples

Example 1

Input: x =[6, 7, 12, 13, 14], revenue = [5, 6, 5, 3, 1], distance = 20, milesRestriction = 5;
Output: 10
Explanation: Choose billboards at positions `6` (revenue 5) and `12` (revenue 5). These two positions are 6 miles apart which satisfies the `milesRestriction = 5` (they must be strictly more than 5 miles apart). Any other selection that tries to include position `7` would conflict with `6` (distance 1) and provides less or equal revenue. Total revenue = 5 + 5 = 10.

Solution

Method 1 — Mile-based DP

Intuition

If you know the maximum revenue MR(i-1) up to mile i-1, then for mile i either there is no billboard placed at i (so MR(i) = MR(i-1)), or there is a billboard at i with revenue r and you must add that to MR(i - (k+1)) (the last mile that is safely more than k miles before i). Iterate miles from 0..M.

Approach

1. Create array mr[0..M] initialized to 0.
2. Maintain an index idx into the sorted x[] billboard positions.
3. For i from 1 to M:
   • If idx < n and x[idx] == i, let r = revenue[idx] and set mr[i] = max(mr[i-1], r + (i-(k+1) >= 0 ? mr[i-(k+1)] : 0)), then idx++.
   • Otherwise set mr[i] = mr[i-1].
4. Answer is mr[M]. To recover chosen sites, scan mr backwards and whenever mr[i] != mr[i-1] a billboard was chosen at i and jump back by k+1 miles.

This approach runs in O(M + n) time and O(M) space.

Code

C++

class Solution {
 public:
  long long maxRevenueByMiles(int M, const vector<int>& x, const vector<int>& r, int k) {
    vector<long long> mr(M+1, 0);
    int idx = 0, n = x.size();
    for (int i = 1; i <= M; ++i) {
      mr[i] = mr[i-1];
      if (idx < n && x[idx] == i) {
        long long take = r[idx] + (i - (k+1) >= 0 ? mr[i-(k+1)] : 0);
        mr[i] = max(mr[i], take);
        ++idx;
      }
    }
    return mr[M];
  }
};

Go

package main

func maxRevenueByMiles(M int, x []int, r []int, k int) int {
    mr := make([]int, M+1)
    idx := 0
    n := len(x)
    for i := 1; i <= M; i++ {
        mr[i] = mr[i-1]
        if idx < n && x[idx] == i {
            take := r[idx]
            if i-(k+1) >= 0 { take += mr[i-(k+1)] }
            if take > mr[i] { mr[i] = take }
            idx++
        }
    }
    return mr[M]
}

Java

class Solution {
  public long maxRevenueByMiles(int M, int[] x, int[] r, int k) {
    long[] mr = new long[M+1];
    int idx = 0, n = x.length;
    for (int i = 1; i <= M; ++i) {
      mr[i] = mr[i-1];
      if (idx < n && x[idx] == i) {
        long take = r[idx] + (i - (k+1) >= 0 ? mr[i-(k+1)] : 0);
        mr[i] = Math.max(mr[i], take);
        ++idx;
      }
    }
    return mr[M];
  }
}

Python

from typing import List

class Solution:
    def max_revenue_by_miles(self, M: int, x: List[int], r: List[int], k: int) -> int:
        mr = [0] * (M + 1)
        idx = 0
        n = len(x)
        for i in range(1, M + 1):
            mr[i] = mr[i-1]
            if idx < n and x[idx] == i:
                take = r[idx]
                if i - (k + 1) >= 0:
                    take += mr[i - (k + 1)]
                mr[i] = max(mr[i], take)
                idx += 1
        return mr[M]

Complexity

• ⏰ Time complexity: O(M + n) — we iterate miles 1..M and process each billboard once.
• 🧺 Space complexity: O(M) for the mr array; recovering the chosen sites needs O(1) extra per chosen site.

Method 2 — Billboard-index DP

Intuition

Treat each billboard as an interval at point xi with profit ri. For billboard i we need the last billboard j < i with x[j] <= x[i] - (k+1). Let p(i) be that index (or 0 if none). Then dp[i] = max(dp[i-1], r[i] + dp[p(i)]) — the standard weighted-interval DP.

Approach

1. Ensure x is sorted. Build p[i] for each i by binary searching the rightmost j < i with x[j] <= x[i] - (k+1).
2. Initialize dp[0] = 0 and iterate i from 1..n computing dp[i] = max(dp[i-1], r[i-1] + dp[p(i)]) (indexing carefully).
3. dp[n] is the answer. Reconstruct chosen billboards by tracing decisions.

This runs in O(n log n) time and O(n) space.

Code

C++

class Solution {
 public:
  long long maxRevenueByIndex(const vector<int>& x, const vector<int>& r, int k) {
    int n = x.size();
    vector<long long> dp(n+1, 0);
    for (int i = 1; i <= n; ++i) {
      int need = x[i-1] - (k+1);
      int lo = 0, hi = i-2, p = 0;
      while (lo <= hi) {
        int mid = (lo+hi)/2;
        if (x[mid] <= need) { p = mid+1; lo = mid+1; } else hi = mid-1;
      }
      dp[i] = max(dp[i-1], r[i-1] + dp[p]);
    }
    return dp[n];
  }
};

Go

package main

import "sort"

func maxRevenueByIndex(x []int, r []int, k int) int {
    n := len(x)
    dp := make([]int, n+1)
    for i := 1; i <= n; i++ {
        need := x[i-1] - (k+1)
        // find rightmost index with x[j] <= need
        j := sort.SearchInts(x, need+1) // returns first > need
        dp[i] = dp[i-1]
        val := r[i-1]
        if j >= 0 { val += dp[j] }
        if val > dp[i] { dp[i] = val }
    }
    return dp[n]
}

Java

import java.util.*;

class Solution {
  public long maxRevenueByIndex(int[] x, int[] r, int k) {
    int n = x.length;
    long[] dp = new long[n+1];
    for (int i = 1; i <= n; ++i) {
      int need = x[i-1] - (k+1);
      int j = Arrays.binarySearch(x, 0, i-1, need + 1);
      if (j < 0) j = -j - 1; // first >= need+1
      long take = r[i-1] + dp[j];
      dp[i] = Math.max(dp[i-1], take);
    }
    return dp[n];
  }
}

Python

from typing import List
import bisect

class Solution:
    def max_revenue_by_index(self, x: List[int], r: List[int], k: int) -> int:
        n = len(x)
        dp = [0] * (n + 1)
        for i in range(1, n+1):
            need = x[i-1] - (k + 1)
            j = bisect.bisect_right(x, need)  # first index > need
            take = r[i-1] + dp[j]
            dp[i] = max(dp[i-1], take)
        return dp[n]

Complexity

• ⏰ Time complexity: O(n log n) due to binary searches for p(i) (or O(n) if p(i) are computed with two pointers for sorted x).
• 🧺 Space complexity: O(n) for the dp and p arrays.