-1

I have numerical segments. For example:

segmetns = [[10,25],[75,270],[11,32],[50,111]]

My task is to count the number of points not occupied by segments.

32-50 in the current situation do not have segments.

I think to implement it with a dictionary. Take the minimum and maximum on the segments (this is easy to get) and replace values in the dictionary if their key is in the range. But I will have to go along the entire length of each of the segments. It is not profitable in time, because segments can be greater than 1 * 10 ^ 12.

Maybe there is the possibility of replacing the range of keys without changing each.

Vasilis G.
  • 7,556
  • 4
  • 19
  • 29
  • 1
    Your question is not clear. By "segment" do you mean a set of consecutive integers? Does the segment `[10,25]` include or exclude the `10` and/or the `25`? What is the overall domain of numbers: the smallest to the largest of all the numbers in your array? What attribute of the segments "can be greater than 1 * 10 ^ 12": the maximum number, the number of small segments, or other? What are the limits on other attributes in your problem? Finally, what exactly is your question to us? – Rory Daulton Nov 25 '18 at 21:13

1 Answers1

0

Take a look at this discussion on SO: python union of multiple ranges

This question talks about finding the union of overlapping intervals. Your question is basically the same. Once you find the union of overlapping intervals, You can easily compute the intervals not covered in your range.

Yakov Dan
  • 2,157
  • 15
  • 29