Interval Trees & Overlap Detection
What is it? (The Analogy)
Imagine you are the school receptionist managing the meeting room schedule. Teachers
book time slots: Ms. Smith wants 9:00-10:30, Mr. Jones wants 10:00-11:00, Mrs. Lee wants
11:00-12:00. When a new booking request comes in, you need to instantly answer: "Does this
overlap with any existing booking?"
If you only have 5 bookings, you can check each one. But what if you have 10,000 bookings
across 50 rooms for the entire semester? Checking every single booking for every new request
would be incredibly slow.
An Interval Tree is like a super-organized filing cabinet for time ranges (or any ranges
of numbers). Instead of searching through every booking, you organize them in a smart tree
structure so that finding all overlapping bookings takes O(log N + K) time, where K is the
number of overlaps found. It is like having a librarian who can instantly tell you which books
cover a specific topic range, without scanning every shelf.
Core idea: An Interval Tree is a balanced binary search tree where each node stores an
interval, and the tree is organized so you can efficiently skip entire branches that
cannot possibly overlap with your query.
Why do we need it?
The Problem: Brute Force Overlap Checking
1// BRUTE FORCE: Check every existing interval for overlap — O(N) per query
2boolean hasOverlap(List<int[]> bookings, int start, int end) {
3 for (int[] booking : bookings) {
4 // Two intervals [a,b] and [c,d] overlap if a < d AND c < b
5 if (booking[0] < end && start < booking[1]) {
6 return true; // Overlap found!
7 }
8 }
9 return false;
10}Cost: O(N) per query. If you have N existing bookings and Q new requests, total cost
is O(N * Q). With 10,000 bookings and 5,000 queries, that is 50 million comparisons.
Simpler Alternative: Sorted List + Binary Search
Before jumping to Interval Trees, there is a simpler approach that works well when intervals
do not overlap (like a single room's calendar):
// If intervals are non-overlapping and sorted, use binary search — O(log N)
// But this ONLY works when existing intervals don't overlap each other!The Full Solution: Interval Trees
When intervals CAN overlap (like bookings across multiple rooms, or overlapping events),
you need an Interval Tree. It handles all cases efficiently.
How it works — Step by Step
An Interval Tree is built on top of a BST (Binary Search Tree) with these modifications:
- Each node stores an interval
[low, high]. - **The BST is ordered by the
lowvalue** of each interval (the start time). - **Each node also stores the maximum
highvalue** in its entire subtree. This is the
secret sauce — it lets us prune branches during search.
- **To search for overlaps with a query interval
[qLow, qHigh]:**
- At each node, check if the node's interval overlaps the query.
- If the left child's max is >= qLow, the left subtree MIGHT have overlaps — go left.
- Otherwise, go right (the left subtree definitely has no overlaps).
- To insert a new interval: Insert like a normal BST (by
lowvalue), then update
the max values going back up.
The overlap condition: Two intervals [a, b] and [c, d] overlap if and only if
a < d AND c < b. Equivalently, they do NOT overlap if a >= d OR c >= b.
Let's Build It Together
Let's build a Restaurant Reservation System where customers book time slots and we need
to detect conflicts.
1/**
2 * Interval Tree for detecting overlapping reservations.
3 *
4 * Scenario: "Pasta Palace" restaurant takes reservations.
5 * Each reservation is a time interval [startHour, endHour].
6 * We need to quickly find if a new reservation conflicts with existing ones.
7 */
8public class IntervalTree {
9
10 /**
11 * Each node in the tree represents one reservation.
12 */
13 static class Node {
14 int low; // Start time of this reservation
15 int high; // End time of this reservation
16 int maxHigh; // Maximum end time in this entire subtree
17 Node left; // Left child (reservations starting earlier)
18 Node right; // Right child (reservations starting later)
19 String guest; // Who made this reservation (for fun!)
20
21 Node(int low, int high, String guest) {
22 this.low = low;
23 this.high = high;
24 this.maxHigh = high; // Initially, max is just this node's high
25 this.guest = guest;
26 this.left = null;
27 this.right = null;
28 }
29 }
30
31 private Node root;
32
33 public IntervalTree() {
34 this.root = null;
35 }
36
37 /**
38 * Insert a new reservation into the tree.
39 *
40 * We insert by 'low' value (start time), just like a regular BST.
41 * After inserting, we update maxHigh values going back up.
42 */
43 public void insert(int low, int high, String guest) {
44 root = insertHelper(root, low, high, guest);
45 }
46
47 private Node insertHelper(Node node, int low, int high, String guest) {
48 // Base case: found an empty spot, create the node
49 if (node == null) {
50 return new Node(low, high, guest);
51 }
52
53 // BST insert: go left if new interval starts earlier, right otherwise
54 if (low < node.low) {
55 node.left = insertHelper(node.left, low, high, guest);
56 } else {
57 node.right = insertHelper(node.right, low, high, guest);
58 }
59
60 // KEY STEP: Update the maxHigh for this subtree
61 // The max could be from this node, or from any descendant
62 node.maxHigh = Math.max(node.maxHigh, high);
63
64 return node;
65 }
66
67 /**
68 * Check if a proposed reservation overlaps with ANY existing one.
69 *
70 * This is the star of the show — O(log N) average case!
71 */
72 public Node findOverlap(int low, int high) {
73 return findOverlapHelper(root, low, high);
74 }
75
76 private Node findOverlapHelper(Node node, int low, int high) {
77 // Base case: reached a null node, no overlap found
78 if (node == null) {
79 return null;
80 }
81
82 // Check if THIS node's interval overlaps with [low, high]
83 // Overlap condition: node.low < high AND low < node.high
84 if (node.low < high && low < node.high) {
85 return node; // Found an overlap!
86 }
87
88 // Decide which subtree to explore:
89 // If the left child exists AND its maxHigh > low,
90 // then there MIGHT be an overlap in the left subtree
91 if (node.left != null && node.left.maxHigh > low) {
92 return findOverlapHelper(node.left, low, high);
93 }
94
95 // Otherwise, try the right subtree
96 return findOverlapHelper(node.right, low, high);
97 }
98
99 /**
100 * Find ALL overlapping reservations (not just the first one).
101 */
102 public List<Node> findAllOverlaps(int low, int high) {
103 List<Node> results = new ArrayList<>();
104 findAllOverlapsHelper(root, low, high, results);
105 return results;
106 }
107
108 private void findAllOverlapsHelper(Node node, int low, int high,
109 List<Node> results) {
110 if (node == null) return;
111
112 // Check this node
113 if (node.low < high && low < node.high) {
114 results.add(node);
115 }
116
117 // Explore left subtree if it might contain overlaps
118 if (node.left != null && node.left.maxHigh > low) {
119 findAllOverlapsHelper(node.left, low, high, results);
120 }
121
122 // Explore right subtree if it might contain overlaps
123 if (node.right != null && node.low < high) {
124 findAllOverlapsHelper(node.right, low, high, results);
125 }
126 }
127}Using it:
1import java.util.*;
2
3public class PastaPalace {
4 public static void main(String[] args) {
5 IntervalTree reservations = new IntervalTree();
6
7 // Existing reservations (hour of day)
8 reservations.insert(17, 19, "Alice"); // 5 PM - 7 PM
9 reservations.insert(12, 14, "Bob"); // 12 PM - 2 PM
10 reservations.insert(20, 22, "Charlie"); // 8 PM - 10 PM
11 reservations.insert(13, 15, "Diana"); // 1 PM - 3 PM
12
13 // New request: Can Eve book 14:00 - 16:00?
14 IntervalTree.Node conflict = reservations.findOverlap(14, 16);
15 if (conflict != null) {
16 System.out.println("Sorry! Conflicts with " + conflict.guest
17 + "'s reservation (" + conflict.low + ":00 - "
18 + conflict.high + ":00)");
19 } else {
20 System.out.println("Reservation confirmed!");
21 }
22
23 // Find ALL conflicts for a proposed 12:30 - 14:30 slot
24 List<IntervalTree.Node> allConflicts =
25 reservations.findAllOverlaps(12, 15);
26 System.out.println("Conflicts found: " + allConflicts.size());
27 for (IntervalTree.Node c : allConflicts) {
28 System.out.println(" - " + c.guest + " ("
29 + c.low + ":00 - " + c.high + ":00)");
30 }
31 }
32}Dry Run / Trace
Building the tree with reservations:
1Insert Alice [17, 19]:
2 [17,19] max=19
3 (Alice)
4
5Insert Bob [12, 14]:
6 [17,19] max=19
7 /
8 [12,14] max=14
9 (Bob)
10
11Insert Charlie [20, 22]:
12 [17,19] max=22 <-- max updated! 22 > 19
13 / \
14 [12,14] [20,22]
15 max=14 max=22
16 (Bob) (Charlie)
17
18Insert Diana [13, 15]:
19 [17,19] max=22
20 / \
21 [12,14] [20,22]
22 max=15 max=22
23 (Bob) (Charlie)
24 \
25 [13,15]
26 max=15
27 (Diana)
28Note: Bob's max updated from 14 to 15 because Diana (15) is in Bob's subtree.Query: findOverlap(14, 16) — "Can we book 2 PM to 4 PM?"
1Start at root: [17, 19] (Alice)
2 Does [17,19] overlap [14,16]?
3 17 < 16? NO. (17 is not less than 16)
4 No overlap with Alice.
5
6 Check left: left.maxHigh = 15. Is 15 > 14? YES.
7 Go LEFT to [12, 14] (Bob)
8
9 Does [12,14] overlap [14,16]?
10 12 < 16? YES. 14 < 14? NO. (14 is not less than 14)
11 No overlap with Bob. (They are adjacent, not overlapping!)
12
13 Check left of Bob: null. Skip.
14 Check right of Bob: [13, 15] (Diana)
15
16 Does [13,15] overlap [14,16]?
17 13 < 16? YES. 14 < 15? YES.
18 OVERLAP FOUND! Diana's reservation [13,15] conflicts.
19 Return Diana's node.Key insight from the trace: Notice how we never even looked at Charlie's reservation
[20, 22]. The tree structure let us skip it entirely because we went left (where the
overlap actually was). This is the power of the maxHigh field — it guides us to the
right branch.
Time & Space Complexity
| Operation | Brute Force | Interval Tree |
|---|---|---|
| Insert | O(1) (append to list) | O(log N) (balanced) |
| Find one overlap | O(N) | O(log N) |
| Find all K overlaps | O(N) | O(log N + K) |
| Space | O(N) | O(N) |
- Search is O(log N) for finding one overlap, because we traverse at most one path from
root to leaf in the tree (like binary search).
- Finding ALL overlaps is O(log N + K) where K is the number of overlaps reported.
- The tree must be balanced for O(log N) guarantees. In practice, use a self-balancing
BST (Red-Black Tree or AVL Tree) as the underlying structure.
- Space is O(N) — each interval gets one node.
Warning: An unbalanced interval tree degrades to O(N) per query. If you insert sorted
intervals (e.g., [1,2], [2,3], [3,4]...), you get a linked list. Always use a balanced
variant in production!
Common Mistakes & Gotchas
- Getting the overlap condition wrong. The correct condition is
a < d AND c < bfor
intervals [a,b) and [c,d). If your intervals are closed (inclusive on both ends),
use a <= d AND c <= b. Be clear about whether endpoints are inclusive or exclusive.
- **Forgetting to update
maxHigh.** After every insert, you must propagate the max value
up the tree. Missing this breaks the search algorithm completely.
- Not balancing the tree. A naive BST can degrade to a linked list. Use AVL or Red-Black
tree balancing, or use a library implementation.
- Confusing "any overlap" with "all overlaps." Finding ONE overlap is O(log N). Finding
ALL overlaps requires visiting multiple branches and is O(log N + K).
- Mixing up open and closed intervals.
[9:00, 10:00)and[10:00, 11:00)do NOT
overlap (half-open intervals). But [9:00, 10:00] and [10:00, 11:00] DO overlap
(closed intervals share the endpoint 10:00). This distinction matters hugely in booking
systems.
Interview Tip
In LLD interviews, you rarely need to implement an Interval Tree from scratch. What
interviewers want to see is that you know when to use one and understand the trade-offs.
Common scenarios: meeting room schedulers, calendar conflict detection, network bandwidth
allocation, and game collision detection. A strong answer mentions: "For overlap queries on
a large number of intervals, I would use an Interval Tree to get O(log N) lookups instead
of O(N)." For simpler cases (non-overlapping intervals, like a single room's schedule), a
sorted list with binary search is often sufficient and simpler to implement.
Quick Quiz
- Think about it: If all reservations are non-overlapping and sorted by start time,
do you still need an Interval Tree? What simpler data structure could you use?
- Design question: How would you handle deleting a reservation from an Interval
Tree? What values need to be updated? (Hint: think about maxHigh.)
- Real-world extension: A meeting room booking system has 10 rooms. How would you
use Interval Trees to find the first AVAILABLE room for a given time slot? Would you
use one tree or ten?
Summary — Key Takeaways
- Interval Trees organize ranges in a BST with an extra
maxHighfield per node that
enables efficient pruning during search.
- Overlap detection drops from O(N) to O(log N) — critical when you have thousands of
intervals and frequent queries.
- **The overlap condition
a < d AND c < b** is the foundation. Memorize it. Pay attention
to whether endpoints are inclusive or exclusive.
- In LLD interviews, knowing WHEN to suggest an Interval Tree is more important than
coding one from scratch. Use it for: booking systems, calendar apps, resource scheduling,
and collision detection.