Skip to main content
Computer Science

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

6
  • $\begingroup$ Do you have a typical value for MAX? Do you have an upper bound on the number of intervals you expect to have in the tree? Since you're asking about optimization down to the individual bit/byte value, knowing concrete numbers can sometimes help, if you know what they will be in your application. That said, if you don't know or want a generic solution because those values will vary greatly, that's an acceptable answer too. $\endgroup$ Commented Jun 13, 2014 at 22:38
  • 1
    $\begingroup$ What happens when an intersection is found? Is the interval still inserted into the data structure? $\endgroup$ Commented Jun 13, 2014 at 22:54
  • $\begingroup$ @StephenBly - if a new interval intersects with existing ones, it won't be inserted and the function will return false. $\endgroup$ Commented Jun 13, 2014 at 23:10
  • $\begingroup$ @D.W. - I don't have typical value of the MAX yet. It should be large enough to justify usage of any new data structure. Number of intervals can grow from 0 to MAX/2 (worst case with all odd points) and then decrease to 1 (full "universe" interval). $\endgroup$ Commented Jun 13, 2014 at 23:20
  • $\begingroup$ @HEKTO If that's the case, then what do you mean "potentially merging it with one or two neighbor intervals"? How can we merge intervals if they don't overlap? $\endgroup$ Commented Jun 13, 2014 at 23:28