CODEWITHSUNDEEP
avl-treeinterval-tree
Steve Andel
Steve Andel

Reputation: 21

Calculate the maximum number of overlapping intervals

Calculate the maximum number of overlapping intervals with some conditions about operations:

  1. Insert an interval: O(logN)
  2. Remove an interval: O(logN)
  3. Calculate(the maximum number of overlapping intervals): O(1)

I think this problem can be solved by using avl tree (suitable for Insert and Remove operations) but I dont know how to design avl tree to satisfy requirement of Calculate operation.

Edit: Example: [start, end)

Input: [1,2),[3,4),[1,6),[3,6),[6,7)

Output: 3

Upvotes: 0

Views: 296

Answers (1)

A Webb
A Webb

Reputation: 711

You need to use a Red Black tree and implement a Point of Maximum Overlap method.

The pseudo-code is in this link. Point of Maximum Overlap

Upvotes: 1

Related Questions