Interval Tree: The Scheduler

The Story: The Overbooked Room

Imagine you manage a conference room. People book it for various times: “9 AM to 11 AM,” “10 AM to 12 PM,” “1 PM to 2 PM.” A new request comes in: “Can I book it from 10:30 AM to 11:30 AM?”

To answer this, you can’t just look at the start times. The 9 AM meeting starts before 10:30, but it ends at 11:00, so it overlaps. The 10 AM meeting also overlaps.

If you have 1,000 bookings, checking them one by one ($O(N)$) is too slow. You need a structure that understands “Span” and “Duration.”

This is the Interval Tree. It is a specialized Binary Search Tree (BST) that stores ranges $[start, end]$ and answers the question: “Does anyone overlap with me?” in $O(\log N)$ time.

Why do we need it?

• Calendars: “Is Luke free between 2 PM and 4 PM?”
• Bioinformatics: “Does this new gene sequence overlap with any known disease markers in the DNA?”
• Window Management: “Which windows on the desktop are clicked by the mouse at position (X, Y)?”

How the Algorithm “Thinks”

The algorithm is a Center-Based Organizer.

1. The Spine: It behaves like a normal BST, sorting intervals based on their low (start) value.
2. The Augmentation: This is the secret sauce. Every node stores an extra piece of information: the Maximum High (End) Value of its entire subtree.

The Search Logic (Is there an overlap with $[L, R]$?):

• Start at the root.
• Does the current node overlap? If yes, return it.
• Go Left? If the left child’s max is greater than my $L$, it means something down there spans far enough to potentially hit me. We must check left.
• Go Right? Otherwise, go right.

This simple “Max” value allows us to ignore entire branches of the tree that “end too early” to matter.

Engineering Context: Segment Tree vs. Interval Tree

Engineers often confuse these two:

• Interval Tree: Stores actual intervals (e.g., specific meetings). Used when intervals are dynamic and you need to find overlaps.
• Segment Tree: Divides space into fixed segments. Used for “Range Queries” (e.g., “What is the sum of array elements from index 5 to 100?”).

Implementation (Python)

class IntervalNode:
    def __init__(self, low, high):
        self.low = low
        self.high = high
        self.max = high # Max end time in this subtree
        self.left = None
        self.right = None

def insert(node, low, high):
    if not node:
        return IntervalNode(low, high)
    
    # Standard BST insert based on 'low'
    if low < node.low:
        node.left = insert(node.left, low, high)
    else:
        node.right = insert(node.right, low, high)
    
    # Update max value for this node
    if node.max < high:
        node.max = high
        
    return node

def search_overlap(node, low, high):
    if not node:
        return None
    
    # Check if current node overlaps
    if node.low <= high and low <= node.high:
        return (node.low, node.high)
    
    # If left child's max is greater than our low, 
    # the answer might be in the left subtree.
    if node.left and node.left.max >= low:
        return search_overlap(node.left, low, high)
    
    return search_overlap(node.right, low, high)

# Usage
root = None
bookings = [(15, 20), (10, 30), (17, 19), (5, 20), (12, 15), (30, 40)]
for l, h in bookings:
    root = insert(root, l, h)

# Check for overlap
query = (14, 16)
print(f"Overlap with {query}: {search_overlap(root, *query)}")
# Likely returns (5, 20) or (10, 30) depending on structure

Summary

The Interval Tree teaches us that to manage time, you need to track the end. By simply remembering the “latest ending time” in a group, we can safely ignore huge chunks of history that are no longer relevant. It reminds us that efficiency comes from knowing what is already “in the past.”