# Interval Tree

###### What is Interval Tree ?
• A tree data structure to hold intervals.
• Used to efficiently find all intervals that overlap with any given interval or point.
• Used in situations when we have a set of intervals and we need following operations to be implemented efficiently.
1. Add an interval
2. Remove an interval
3. Given an interval x, find if x overlaps with any of the existing intervals.
###### Why Interval Trees ?
• By augmenting a self-balancing Binary Search Tree (BST) like Red Black Tree, AVL Tree, we can maintain set of intervals so that all operations can be done in O(Logn) time.

• Every node of Interval Tree stores following information:

• i: An interval which is represented as a pair [low, high]
• max: Maximum high value in subtree rooted with this node.
• The low value of an interval is used as key to maintain order in BST.

• The insert and delete operations are same as insert and delete in self-balancing BST used.

#### Applications

• Used for windowing queries like:
• To find all roads on a computerized map inside a rectangular viewport.
• To find all visible elements inside a three-dimensional scene.
###### Interval Tree vs Segment Tree
• Both segment and interval trees store intervals.
• Segment tree is mainly optimized for queries for a given point.
• Interval trees are mainly optimized for overlapping queries for a given interval.

## 1. Find Conflicting Appointments***

###### Problem:

Given n appointments, find all conflicting appointments.

An appointment is conflicting, if it conflicts with any of the previous appointments in array.

Example:

Input: appointments[] = { {1, 5}, {3, 7}, {2, 6}, {10, 15}, {5, 6}, {4, 100} }
Output: Following are conflicting intervals
[3,7] Conflicts with [1,5]
[2,6] Conflicts with [1,5]
[5,6] Conflicts with [3,7]
[4,100] Conflicts with [1,5]

###### Approach-1: Brute-Force
• For every appointment check if it conflicts with any other appointement by processing all appointements one-by-one.
• Time Complexity: O(n2)
###### Approach-2: Interval Tree
• Create an Interval Tree, initially with the first appointment.
• Do following for all other appointments starting from the second one.
• a) Check if the current appointment conflicts with any of the existing appointments in Interval Tree. If conflicts, then print the current appointment. This step can be done O(Logn) time.
• b) Insert the current appointment in Interval Tree. This step also can be done O(Logn) time.
• Need to do it for n elements and hence O(nlogn) total time.
• Time Complexity: O(nlogn)
###### Implementation:
``````class IntervalTreeNode:
def __init__(self, low, high):
self.low = low
self.high = high
self.left = None
self.right = None

def insert(root, low, high):
if not root:
return IntervalTreeNode(low, high)

if low <= root.low:
root.left = insert(root.left, low, high)
else:
root.right = insert(root.right, low, high)

return root

def find_conflicting_appointment(root, low, high):
while root:
if(root.low < high and low < root.high):
print("[{}, {}] Conflicts with [{}, {}]".format(low, high, root.low, root.high))
return
elif low <= root.low:
root = root.left
else:
root = root.right

def conflicting_appointments(root, appointments):
for appointment in appointments:
low = appointment[0]
high = appointment[1]
find_conflicting_appointment(root, low, high)
root = insert(root, low, high)

print("Exampl-1: Conflicting Appointments - Interval Tree")
appointments = [(1, 5), (3, 7), (2, 6), (10, 15), (5, 6), (4, 100)]
conflicting_appointments(None, appointments)
``````

Output:

###### Complexity:
• Time: O(nlogn)
• Auxilliary Space: O(1)
##### Notes:
• Time complexity of the above implementation may be more than O(nLogn) if skewed trees.
• To avoid that we can use Red-Black Tree or AVL Tree balancing techniques.