There is a linear mono-dimensional space ranging from 0 to 100. In this space exist several points:
2.34
14.5
15.3
39.02
54.55
55.67
89.11
91.1
Each of these points can be moved along the space by +/-1 unit which we call ranges, like:
2.34 can be placed from 1.34 till 3.34
14.5 can be placed from 13.5 till 15.5
15.3 can be placed from 14.3 till 16.3
... and so on.
If we want to find the smallest sub-collection of segments that cover all the points, this represent a Set Cover problem, that can be solved by a greedy algorithm. In R I would do something like this
library(data.table)
library(RcppGreedySetCover)
#my points collection
Points = c(2.34, 14.5, 15.3, 39.02, 54.55, 55.67, 89.11, 91.1)
#ranges in which points can exists
rangesMIN <- unlist(lapply(Points, function(x) seq(x-1, (x + 0.0001 - x %% 0.0001), by = 0.0001)))
rangesMAX <- rangesMIN + 2
#segments
Segs <- data.table(segments = paste0(rangesMIN, "_", rangesMAX),
element = rep(Points, unlist(lapply(Points, function(z) length(unlist(lapply(z, function(x) seq(x-1, (x + 0.0001 - x %% 0.0001), by = 0.0001))))))))
unique(greedySetCover(Segs, F)$segments)
which gives:
[1] "1.34_3.34" "14.3_16.3" "38.02_40.02" "53.55_55.55" "54.67_56.67" "88.11_90.11" "90.1_92.1"
All these segments contain the points, fine. Now, if each point is associated with a 'weight', e.g.
2.34 (152)
14.5 (1568)
15.3 (99)
...
and I want to find the smallest sub-collection of segments that cover all the points, avoiding points with too different weights (max 2 fold difference) to be present in the same covering segment, is this still a set cover problem?