python - Pick optimize minimum number of elements to span a region -

i have optimization problem. have never learned algorithms, taught myself python, not sure if hard or easy problem solve. non-abstract application of problem determining cheapest way sequence dna using available reagents. problem...

there circular region, 0-10, 10 loops 0. there elements of length 1, each spans part of region , ultimate goal minimize number of elements while covering every position. have number of elements of length 1, these elements not cover whole region. therefore, need add additional elements, @ cost.

so final cost (number of elements) + 2(number of elements purchased) , goal minimize cost. easy problem solve, or require significant effort solve it?

so in example, pick add value @ 2 , 5.75, , remove values @ 2.5.

i don't know python, can pseudo-code. might not perfectly optimal constraints, can tweak around if needed.

let's assume elements have 2 properties, begin , end, define x-coordinate respectively, well, begin , end! (even though end begin+1. if element starts @ 9.5, consider ending @ 10.5 instead of 0.5)

put elements array elem[] , sort them lower begin first. copy first element , put @ end of array increasing 10 on both begin , end coordinates. (so might become 10.2 through 11.2) cover circular aspect of problem, use reference not count twice in costs.

x = 0  (the farthest have got covered far) foreach element in array, in order, except last element:   if elem[i+1].begin <= x     continue; // means dont need current element, discard , go next iteration of loop.   if elem[i].begin <= x     x = elem[i].end // use element expand reach   else // bad news, got empty hole     add_elements += ceil(elem[i].begin - x)  // ceil = round integer number of elements needed cover hole     x = elem[i].end // use element anyway!  if x < 10 // after loop ends   add_elements += ceil(elem[last].begin - x) 

you can rewrite last if/else require if, thought way more didactic , easier understand.

add_elements contains how many elements need add. ceil() function if have continuous hole of length 2.4, know need @ least 3 new elements fix that.

this algorithm simple , quick, time complexity of o(n logn) due initial sorting, since not know how many elements need handle. can't cheaper floating point coordinates.

possibility of improvement: when know there hole must add new elements fix, might possible discard picked element, either @ beginning and/or end of hole. example, consider elements {(0,1), (0.7, 1.7), (1.8, 2.8), (2,3)}. there hole of length 0.1 between second , third elements, if add new element of length 1 , place between 1.0 , 2.0, can throw out both second , third elements.