There is a range of numbers (type double) from 0 to 500. In the process of the program, small intervals are created, for example, from 4.537 to 7.654, or from 121.346 to 156.234

It is necessary in a large range (0-500) to "reserve" these "small" intervals.

And when the next "small" interval is formed, check, and not whether the place is "occupied" in the "large" range. If "busy", then "take" at least the remainder.

For example: someone occupied in a large range from 20 to 30, and new data want to take from 25 to 40, then the area from 20 to 40 should be marked as occupied.

How best to organize it?

  • Just now I noticed the word "in the array" in the title. And this is important, is it necessary to use an array? - m. vokhm
  • Not necessarily, it just seems to me that the easiest way to work with him. In general, I think I figured out how to do it. Will I make an array of boolean types? The size of the array is 500 * 100 = 50000. The value of the beginning of the ranges and the end is simply multiplied by 100 or 1000 so as not to lose the comma, and then divide back when I take the value. - kaaa
  • The case is a master, but it seems to me that what I proposed is both simpler, more flexible and more reliable. If you, for example, need to take an interval of 0.00001234 .. 0.00002384736, what will you do? And if tomorrow you want to use the range not from 0 to 500, but from -1000000 to 1000000 - how much memory will you need to buy into the car? - m. vokhm
  • Estimate the memory consumption and execution time for both. If you need to check for employment the entire range from 0 to 500 in increments of 0.001, will you have to do 500,000 checks? - m. vokhm
  • Yes, your option is more optimal, I agree. - kaaa

1 answer 1

There can be many solutions, how to organize better - in general, it cannot be said, since the criteria for "best" may be different. One of the possible solutions (the first one that came to mind) is to represent occupied ranges as pairs of numbers '[beginning of range, end of range]', for example Map.Entry<Double, Double> and store them in an ordered dictionary, you can in 'TreeMap'.

In this case, the code for reserving the range may be something like this:

 Map.Entry<Double, Double> occupy(Double rangeStart, Double rangeEnd) { Map.Entry<Double, Double> floor = map.floorEntry(rangeStart); if (floor != null && floor.getValue() >= rangeStart) { map.remove(floor.getKey()); rangeStart = Math.min(floor.getKey(), rangeStart); rangeEnd = Math.max(floor.getValue(), rangeEnd); } Map.Entry<Double, Double> ceiling = map.ceilingEntry(rangeStart); if (ceiling != null && ceiling.getKey() <= rangeEnd) { map.remove(ceiling.getKey()); rangeEnd = Math.max(ceiling.getValue(), rangeEnd); } map.put(rangeStart, rangeEnd); return map.ceilingEntry(rangeStart); }

And the code to check whether the range you are interested in is busy or not. It may look something like this:

 /** Checks if the whole range is occupied -- no free areas */ boolean isFree(Double rangeStart, Double rangeEnd) { Map.Entry<Double, Double> floor = map.floorEntry(rangeStart); if (floor != null && floor.getValue() >= rangeStart) return false; Map.Entry<Double, Double> ceiling = map.ceilingEntry(rangeStart); if (ceiling != null && ceiling.getKey() <= rangeEnd) return false; return true; } /** Checks if the whole range is free -- no occupied areas */ boolean isOccupied(Double rangeStart, Double rangeEnd) { Map.Entry<Double, Double> floor = map.floorEntry(rangeStart); if (floor != null && floor.getValue() >= rangeEnd) return true; return false; }

A working snippet with a couple of additional methods and a minimalist test suite can be found at http://ideone.com/3arRnM . I cannot vouch for the loyalty and beauty of the code - the idea is not very thought out and implemented hastily. Think, induce beauty and test further yourself.