Cellphone base covering
MediumUpdated: Aug 2, 2025
Problem
Given the following data:
- An array representing the positions of
Nhouses along a line. - An array representing the positions of
Msuitable places along the line where base transmitters can be placed. - An array representing the respective
Mcosts to build and place a base transmitter. - The radius
Rof coverage for a base, meaning a base at positionxcan serve all houses between[x - R, x + R].
Objective: Determine the minimum cost to provide coverage to all houses using the base stations, or report that it's not possible.
Examples
Example 1
Input:
houses = [1, 5, 10]
bases = [3, 7, 11]
costs = [1, 2, 3]
radius = 3
Output:
3
Explanation:
- We can place base transmitters at positions 3, 7, and 11.
- Base at position 3 with a cost of 1 covers house 1 and house 5.
- Base at position 11 with a cost of 3 covers house 10.
- Total cost = 1 + 3 = **3**.
Solution
Method 1 - Using Dynamic Programming
The optimal solution can be derived recursively by addressing one house at a time. A prerequisite for the algorithm is to ensure that the houses, bases, and their corresponding costs are sorted.
For the first house, the minimum cost is straightforward: since no previous solution exists with zero houses, we simply select the cheapest base capable of covering it. For the second house, the solution depends on the following:
- The previous solution already covers this house — making it the best possible choice.
- The new house lies outside the range of the previous solution’s base — we must find the next cheapest base that provides coverage.
- No base is available to cover the house — the problem is unsolvable with the given input.
Reasoning or Intuition
- Each house must be covered by at least one transmitter. For a base at position
x, it can serve houses within[x - R, x + R]. - The goal is to pick a subset of transmitters to minimise the total cost while ensuring all houses get covered.
- The problem can be modelled as a minimum cost coverage problem, akin to a "set cover problem," which can be solved efficiently in most cases using a greedy or a dynamic programming approach.
Approach
- Sort and Pre-process Data:
- Sort the houses in ascending order.
- Gather coverage information for each base — determine the range
[x - R, x + R]for each base and the houses it can cover.
- Dynamic Programming Approach:
- Use a DP table where
dp[i]represents the minimum cost to cover the firstihouses. - For each base, try placing the transmitter and update the costs based on the houses it covers.
- If a base does not contribute to covering houses, skip it.
- Use a DP table where
- Greedily Select Bases (as Alternative):
- Pick the cheapest base that provides maximum additional coverage until all houses are covered.
Code
C++
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
using namespace std;
class Solution {
public:
int minCostToCoverHouses(vector<int>& houses, vector<int>& bases, vector<int>& costs, int radius) {
sort(houses.begin(), houses.end());
vector<pair<int, int>> basesWithCosts;
// Pair bases with costs and sort by positions
for (int i = 0; i < bases.size(); i++) {
basesWithCosts.emplace_back(bases[i], costs[i]);
}
sort(basesWithCosts.begin(), basesWithCosts.end());
// Dynamic Programming: Initialize with infinity
int n = houses.size();
vector<int> dp(n + 1, numeric_limits<int>::max());
dp[0] = 0; // No cost to cover 0 houses
for (auto& base : basesWithCosts) {
int basePos = base.first, cost = base.second;
int coverStart = basePos - radius, coverEnd = basePos + radius;
vector<int> newDP = dp; // Copy to a new DP state
for (int i = 0; i < n; i++) {
if (houses[i] >= coverStart && houses[i] <= coverEnd) {
// Update the DP state
newDP[i + 1] = min(newDP[i + 1], dp[i] + cost);
}
}
dp = newDP;
}
return dp[n] == numeric_limits<int>::max() ? -1 : dp[n];
}
};
int main() {
Solution solution;
vector<int> houses = {1, 5, 10};
vector<int> bases = {3, 7, 11};
vector<int> costs = {1, 2, 3};
int radius = 3;
cout << "Minimum cost: " << solution.minCostToCoverHouses(houses, bases, costs, radius) << endl;
return 0;
}
Go
package main
import (
"fmt"
"math"
"sort"
)
type Base struct {
position int
cost int
}
type Solution struct{}
func (s Solution) MinCostToCoverHouses(houses []int, bases []int, costs []int, radius int) int {
sort.Ints(houses)
// Create a sorted slice of bases with costs
n, m := len(houses), len(bases)
basesWithCosts := make([]Base, m)
for i := 0; i < m; i++ {
basesWithCosts[i] = Base{
position: bases[i],
cost: costs[i],
}
}
sort.Slice(basesWithCosts, func(i, j int) bool {
return basesWithCosts[i].position < basesWithCosts[j].position
})
// Initialize DP (Dynamic Programming) states
dp := make([]int, n+1)
for i := 1; i <= n; i++ {
dp[i] = math.MaxInt32
}
// Iterate over each base for coverage
for _, base := range basesWithCosts {
coverStart := base.position - radius
coverEnd := base.position + radius
newDP := make([]int, n+1)
copy(newDP, dp)
for i := 0; i < n; i++ {
if houses[i] >= coverStart && houses[i] <= coverEnd {
newDP[i+1] = min(newDP[i+1], dp[i]+base.cost)
}
}
dp = newDP
}
if dp[n] == math.MaxInt32 {
return -1
}
return dp[n]
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func main() {
houses := []int{1, 5, 10}
bases := []int{3, 7, 11}
costs := []int{1, 2, 3}
radius := 3
solution := Solution{}
fmt.Println("Minimum cost:", solution.MinCostToCoverHouses(houses, bases, costs, radius))
}
Java
class Solution {
public int minCostToCoverHouses(int[] houses, int[] bases, int[] costs, int radius) {
int n = houses.length;
int m = bases.length;
Arrays.sort(houses);
// Pair base positions with costs
List<int[]> basesWithCosts = new ArrayList<>();
for (int i = 0; i < m; i++) {
basesWithCosts.add(new int[]{bases[i], costs[i]});
}
basesWithCosts.sort((a, b) -> Integer.compare(a[0], b[0]));
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int[] base : basesWithCosts) {
int basePos = base[0];
int cost = base[1];
int coverStart = basePos - radius;
int coverEnd = basePos + radius;
int[] newDp = Arrays.copyOf(dp, dp.length);
for (int i = 0; i < n; i++) {
if (houses[i] >= coverStart && houses[i] <= coverEnd) {
newDp[i + 1] = Math.min(newDp[i + 1], dp[i] + cost);
}
}
dp = newDp;
}
return dp[n] == Integer.MAX_VALUE ? -1 : dp[n];
}
}
Kotlin
import kotlin.math.min
class Solution {
fun minCostToCoverHouses(houses: IntArray, bases: IntArray, costs: IntArray, radius: Int): Int {
// Sort houses and pair the bases with their costs
houses.sort()
val basesWithCosts = bases.zip(costs).sortedBy { it.first }
val n = houses.size
val m = bases.size
val INF = Int.MAX_VALUE
// DP Array: dp[i] represents the minimum cost to cover first i houses
val dp = IntArray(n + 1) { INF }
dp[0] = 0 // Base case: 0 houses require 0 cost
// Iterate over each base
for ((base, cost) in basesWithCosts) {
val coverStart = base - radius
val coverEnd = base + radius
val newDP = dp.copyOf()
// Update DP state for each house
for (i in houses.indices) {
if (houses[i] in coverStart..coverEnd) {
newDP[i + 1] = min(newDP[i + 1], dp[i] + cost)
}
}
dp.indices.forEach { dp[it] = newDP[it] }
}
return if (dp[n] == INF) -1 else dp[n]
}
}
fun main() {
val solution = Solution()
val houses = intArrayOf(1, 5, 10)
val bases = intArrayOf(3, 7, 11)
val costs = intArrayOf(1, 2, 3)
val radius = 3
println("Minimum cost: ${solution.minCostToCoverHouses(houses, bases, costs, radius)}")
}
Python
class Solution:
def minCostToCoverHouses(self, houses, bases, costs, radius):
n, m = len(houses), len(bases)
# Sort based on base position
bases_with_costs = list(zip(bases, costs))
houses.sort()
bases_with_costs.sort()
# DP to track house-cover costs
INF = float('inf')
dp = [INF] * (n + 1)
dp[0] = 0
for j, (base, cost) in enumerate(bases_with_costs):
cover_start = base - radius
cover_end = base + radius
new_dp = dp[:]
for i in range(n):
if houses[i] >= cover_start and houses[i] <= cover_end:
# This base can potentially cover house i
new_dp[i + 1] = min(new_dp[i + 1], dp[i] + cost)
dp = new_dp
return dp[n] if dp[n] != INF else -1
Rust
struct Solution;
impl Solution {
pub fn min_cost_to_cover_houses(houses: Vec<i32>, bases: Vec<i32>, costs: Vec<i32>, radius: i32) -> i32 {
let mut houses = houses;
let mut bases_with_costs: Vec<(i32, i32)> = bases.into_iter().zip(costs.into_iter()).collect();
houses.sort(); // Sort houses
bases_with_costs.sort(); // Sort bases with their costs
let n = houses.len();
let inf = i32::MAX;
let mut dp = vec![inf; n + 1];
dp[0] = 0;
for (base, cost) in bases_with_costs {
let cover_start = base - radius;
let cover_end = base + radius;
let mut new_dp = dp.clone();
for i in 0..n {
if houses[i] >= cover_start && houses[i] <= cover_end {
new_dp[i + 1] = min(new_dp[i + 1], dp[i] + cost);
}
}
dp = new_dp;
}
if dp[n] == inf {
-1
} else {
dp[n]
}
}
}
fn main() {
let houses = vec![1, 5, 10];
let bases = vec![3, 7, 11];
let costs = vec![1, 2, 3];
let radius = 3;
let result = Solution::min_cost_to_cover_houses(houses, bases, costs, radius);
println!("Minimum cost: {}", result);
}