Cellphone base covering

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

#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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

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))
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

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];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

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)}")
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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  # 0 houses cost 0 to cover
        
        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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

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);
}