calculating the least amount routers needed to reach a set of buildings-CodePudding

I have range = n and a numlist x = [2,4,5,6,7,9,11,12] and another numlist y = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14] (from range 0 to max(x) n 1) and I want to output the least amount of routers I would have to put to reach the buildings in numlist x and on which building I would put them on (I would only put them on buildings in numlist x) given that each router had the range n. If range here was 2 then a router on building 2 would only reach buildings 2 and 4. If I had a router on building 6 then the router would reach buildings 4,5,6,7,8 and so on. (the buildings from numlist x are the ones that matter, numlist y is only there as a reference). So far I have this.

needed_towers = [2,4,5,6,7,9,11,12]
towers =  [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14] #only used here to get the intersect between the needed towers and towers so i can remove the unneeded numbers from the dictionary values 
intersect = set(towers) - set(needed_tows)

r = 2
ans = []
placed = {}
a = [list(range(i-r,i   r   1)) for i in needed_tows]

for i in a:
    for j in intersect:
        if j in i:
            i.remove(j)

for i,x in zip(needed_tows,a):
    placed[i] = x

#if needed_tows was [1,2,3,4,5] one of the solutions would be 2,5 or 2,4 and a few other solutions but i only need one.

this program just calculates which buildings a router would reach if it were placed on each building and places the values in a dictionary, the next step would be to calculate what the buildings i need to place them on. technically there are many solutions to this such as [4,9,12] or even [4,9,11] and a few more but as long as its the shortest solution possible it doesn't matter. How do I write a program to calculate which buildings I would have to place routers on so each building is reached?

CodePudding user response：

You can try this:

from bisect import bisect

x = [2, 4, 5, 6, 7, 9, 11, 12]
r = 2

out = []
while x:
    idx = -1 if (n := x[0]   r) > x[-1] else bisect(x, n) - 1
    out.append(x[idx])
    x = x[bisect(x, out[-1]   r):]

print(out)

It gives:

[4, 9, 12]