CODEWITHSUNDEEP
algorithmcomputational-geometry
KodeWarrior
KodeWarrior

Reputation: 3598

Finding all the intervals that does not overlap with the point

I have intervals of the form (a1, b1), (a2, b2), ...., (an, bn).
I would like to support the following operations

  1. Adding a new interval.
  2. Deleting an existing interval.
  3. Given a point, find all intervals that do not overlap with the point.

Intervals tree is the straightforward solution if we want to find intervals which overlap with the point. What about the case when we want to find non intersecting intervals?

Upvotes: 2

Views: 115

Answers (1)

shapiro yaacov
shapiro yaacov

Reputation: 2346

Have all nodes in two trees simultaneously. Tree A holds them by key ai and tree B holds them by key bi.
Insertion and deletion is obviously O(log n).
For requirement 3, print the nodes in B from the smallest to the biggest and stop when bi is still smaller then the point. Same, but backwards, in A.

Example:
Given (1,10), (5,18), (13,20), and a point 12.
The interval(s) in A where ai is bigger than 12 is (13,20), and in B the interval(s) that are smaller are (1,10).

Upvotes: 3

Related Questions