Interval Tree: Managing Overlapping Intervals Efficiently

Interval data appears whenever something remains valid across a continuous range. A calendar event occupies a period of time. A reservation uses a resource between two boundaries. A network rule may apply across an address range. A measurement may describe a section of a line or timeline. In each case, the basic object is an interval:

[start, end]

A common operation is to determine whether one interval overlaps any interval already stored. For a calendar, the question might be: “Does this proposed meeting conflict with an existing event?” Another useful operation is to return every stored interval that overlaps a query interval.

A simple list can answer these questions by checking every interval one by one. That approach is easy to understand, but it provides no structural reason to stop early. An interval tree improves the organization of the data by combining two ideas:

1. Store intervals in a tree ordered by one endpoint, commonly the start value.
2. Store an additional summary in each subtree: the largest end value found anywhere in that subtree.

This summary is commonly called maxEnd or max. It enables pruning. During a query, the tree can prove that an entire subtree is irrelevant and skip it without inspecting every interval inside it.

The central invariant is:

node.maxEnd = the largest end value in node's entire subtree

If the invariant is maintained correctly, an interval query can use subtree summaries to avoid unnecessary work. This article explains the tree shape, the invariant, construction, insertion, deletion, overlap queries, endpoint conventions, validation, and practical calendar usage.

1. Understanding Intervals​

An interval contains a beginning and an ending boundary. A calendar event might be represented as:

[09:00, 10:30]

The interval starts at 09:00 and ends at 10:30. For algorithmic examples, times can also be represented numerically:

[9, 10.5]

The interval-tree structure does not depend on whether the endpoints are integers, decimal values, timestamps, or another ordered type. What matters is that the endpoints can be compared consistently.

Before implementing an interval tree, the application should decide how endpoints behave. Several conventions are common:

• A closed interval includes both endpoints: [start, end].
• An open interval excludes both endpoints: (start, end).
• A half-open interval includes the start and excludes the end: [start, end).

The tree can support these conventions, but the overlap predicate and pruning comparisons must use the same convention.

For closed intervals, two intervals A and B overlap when:

A.start <= B.end and B.start <= A.end

They do not overlap when one lies completely before the other:

A.end < B.start or B.end < A.start

For half-open intervals, the overlap test is commonly written as:

A.start < B.end and B.start < A.end

This difference matters when two intervals touch. Under half-open semantics, these intervals are adjacent but do not overlap:

[09:00, 10:00)
[10:00, 11:00)

The data structure remains the same, but equality at a boundary changes the result. A calendar implementation should document its endpoint policy before writing query logic.

2. Why Use a Tree Instead of a List?​

Imagine a calendar containing the following events:

[08:00, 09:00]
[09:30, 10:15]
[11:00, 12:00]
[13:00, 14:30]
[15:00, 16:00]

To test a proposed event such as [09:45, 11:15], a list-based implementation scans each stored interval and applies the overlap test. That is perfectly reasonable for a small collection.

The problem is that a list contains no summary information. After checking several non-overlapping events, the remaining intervals may still contain a match. The algorithm cannot generally reject a large group of entries at once. Queries therefore tend to inspect a broad portion of the collection.

An interval tree adds structure. Ordering by start time allows the search to move through a hierarchy. The maxEnd value gives the search information about an entire subtree. If the latest ending interval in a subtree still ends before the query begins, then every interval in that subtree ends too early to overlap the query.

The tree does not eliminate the need to test individual candidate intervals. It makes a stronger kind of conclusion possible: instead of proving that one interval does not overlap, it can prove that a whole subtree cannot contain an overlap.

That distinction is the source of the efficiency improvement.

3. The Shape of an Interval Tree​

A common interval-tree design uses a binary search tree ordered by interval start. Each node stores at least:

interval.start
interval.end
left child
right child
maxEnd

The ordering rule is usually:

• an interval with a smaller start goes to the left;
• an interval with a larger start goes to the right;
• intervals with equal starts follow a defined tie-breaking policy.

The tie-breaking policy might compare end values, place equal-start intervals consistently on one side, or store several intervals together at one key. The specific policy can vary. What matters is that insertion, searching, validation, and updates all follow the same rule.

Consider these intervals inserted in the displayed order:

A = [09:00, 10:00]
B = [08:00, 08:45]
C = [11:00, 12:00]
D = [09:30, 11:30]

A possible tree shape is:

          A [09:00, 10:00]
         /                 \
B [08:00, 08:45]       C [11:00, 12:00]
                              /
                     D [09:30, 11:30]

The left subtree contains earlier starts, while the right subtree contains later starts according to the chosen ordering policy. This is the ordinary search-tree part of the structure.

The exact shape depends on insertion order. Inserting the same intervals in a different order can produce a different tree. The interval-tree idea does not depend on one particular shape, although the shape influences how much work a search may require.

It is useful to separate two concerns:

• Ordering invariant: nodes appear in the correct position according to their start values.
• Augmentation invariant: every node's maxEnd correctly summarizes its subtree.

Both invariants are necessary. A correctly ordered tree with incorrect summaries cannot prune safely. Correct summaries attached to an incorrectly ordered tree cannot support the intended directional search rules.

4. The maxEnd Invariant​

For a node x, the summary is defined as:

x.maxEnd = maximum of:
           x.interval.end,
           x.left.maxEnd, if a left child exists,
           x.right.maxEnd, if a right child exists

In other words, maxEnd is the largest ending value anywhere below or at the node. It is not necessarily the end of the interval stored directly in that node.

Using the earlier tree:

          A [09:00, 10:00]
         /                 \
B [08:00, 08:45]       C [11:00, 12:00]
                              /
                     D [09:30, 11:30]

The summaries are:

• B.maxEnd = 08:45, because B is a leaf.
• D.maxEnd = 11:30, because D is a leaf.
• C.maxEnd = 12:00, because its own interval ends at 12:00 and its child ends at 11:30.
• A.maxEnd = 12:00, because the largest ending value in the whole tree is 12:00.

The augmented tree is therefore:

                 A [09:00, 10:00], maxEnd=12:00
                /                              \
B [08:00, 08:45], maxEnd=08:45    C [11:00, 12:00], maxEnd=12:00
                                                  /
                              D [09:30, 11:30], maxEnd=11:30

The summary is computed from the bottom upward. Leaf nodes are easy: their maxEnd equals their own end. An internal node combines its own end with the summaries of its children.

This invariant must be restored after every operation that changes the subtree. Insertions can increase a summary. Deletions can decrease one. Rotations or other structural changes can require summaries to be recomputed even when no interval endpoint itself changes.

5. How maxEnd Enables Pruning​

Suppose a query interval begins at 10:30:

Q = [10:30, 11:15]

Now imagine that the left child of the current node represents a subtree with:

left.maxEnd = 09:45

That value means every interval in the left subtree ends at or before 09:45. Since all of them end before the query begins at 10:30, none can overlap Q.

The entire left subtree can be skipped.

The safe pruning condition for a closed-interval interpretation is conceptually:

subtree.maxEnd < query.start

For a different endpoint convention, the equality comparison may change. The principle is unchanged: if the subtree's latest possible ending point is too early to reach the query, the subtree is irrelevant.

The converse is important. If:

subtree.maxEnd >= query.start

that does not prove that an overlap exists. It only means that the subtree cannot be ruled out using its summary. The search must examine appropriate nodes and apply the actual overlap predicate.

Thus, maxEnd is a certificate of impossibility when it is too small. It is not a certificate of a match when it is large enough.

6. Building the Tree Through Insertion​

Construction starts with an empty tree. Each interval is inserted according to its start value. Once the new node has been placed, its maxEnd is initialized and the values of its ancestors are recomputed on the path back to the root.

For a leaf:

node.maxEnd = node.interval.end

For an internal node:

node.maxEnd = max(
    node.interval.end,
    node.left.maxEnd if left exists,
    node.right.maxEnd if right exists
)

Inserting the first event​

Insert:

[09:00, 10:00]

The tree contains one node:

[09:00, 10:00], maxEnd=10:00

Because there are no children, the node's own end is the subtree maximum.

Inserting an earlier event​

Insert:

[08:00, 08:45]

The start value 08:00 is earlier than 09:00, so the new event becomes the left child:

        [09:00, 10:00], maxEnd=10:00
       /
[08:00, 08:45], maxEnd=08:45

The root's summary remains 10:00 because 10:00 is greater than 08:45.

Inserting a later event​

Insert:

[11:00, 12:00]

It becomes the right child:

        [09:00, 10:00], maxEnd=12:00
       /                         \
[08:00, 08:45], maxEnd=08:45  [11:00, 12:00], maxEnd=12:00

The root's maxEnd changes to 12:00 because the new right subtree contains the largest endpoint.

Inserting a long interval with an early start​

Now insert:

[08:30, 13:00]

Its start is after 08:00 but before 09:00, so it belongs within the left side according to the ordering rule. Its end, 13:00, is larger than every endpoint previously stored. That value must propagate through its ancestors:

        [09:00, 10:00], maxEnd=13:00
       /                         \
  left subtree maxEnd=13:00    [11:00, 12:00], maxEnd=12:00

This example shows why the summary must cover the entire subtree. The interval with the largest endpoint may be far below the root and may have an earlier start than many other intervals.

7. Querying for One Overlap​

A one-result query asks whether any stored interval overlaps a query interval. It can return as soon as it finds the first match.

At each visited node:

1. Test the node's interval against the query.
2. If they overlap, return the node or its associated calendar event.
3. If they do not overlap, determine whether the left subtree could still contain a match.
4. Use the maxEnd summary to prune the left subtree when possible.
5. Continue into the remaining relevant direction.

A common search rule is:

if left exists and left.maxEnd >= query.start:
    search left
otherwise:
    search right

The comparison shown assumes a closed-style boundary policy. Adjust it for the chosen endpoint semantics.

Step-by-step example​

Use this tree:

                 A [09:00, 10:00], maxEnd=12:00
                /                              \
B [08:00, 08:45], maxEnd=08:45    C [11:00, 12:00], maxEnd=12:00
                                                  /
                              D [09:30, 11:30], maxEnd=11:30

Query:

Q = [10:30, 10:45]

The search proceeds as follows:

1. Compare Q with A = [09:00, 10:00]. The intervals do not overlap because A ends before 10:30.
2. Inspect the left subtree. Its maxEnd is 08:45.
3. Since 08:45 is before the query start of 10:30, every interval in that subtree ends too early. Skip it.
4. Move to the right subtree.
5. Compare Q with C = [11:00, 12:00]. This interval starts after the query ends, so it does not overlap.
6. Examine the relevant child, D = [09:30, 11:30].
7. D overlaps the query because it begins before 10:45 and ends after 10:30.

The search never needed to inspect B. Its subtree summary proved that B could not be a match.

8. Querying for All Overlaps​

A conflict-detection tool may need every overlapping event rather than just one. For example, a proposed meeting might conflict with several existing events, and the user may need a complete list.

An all-overlaps traversal continues after finding a match, but it uses the same pruning rules. A conceptual recursive procedure is:

searchAll(node, query):
    if node is empty:
        return

    if node.left exists and node.left.maxEnd >= query.start:
        searchAll(node.left, query)

    if overlaps(node.interval, query):
        report node.interval

    if node.interval.start <= query.end:
        searchAll(node.right, query)

The first condition protects against searching a left subtree whose intervals all end too early. The second checks the current interval. The third uses start-time ordering: if the current node starts after the query ends, later nodes in the right subtree generally start even later and cannot overlap.

Again, endpoint equality must be handled consistently. For half-open intervals, the right-subtree condition commonly uses a strict comparison rather than the closed-interval comparison shown above.

Calendar example​

Suppose a calendar contains:

Team meeting:      [09:00, 10:00]
Design review:     [09:30, 11:30]
Customer call:     [10:45, 11:15]
Lunch:             [12:00, 13:00]
Planning session:  [14:00, 15:00]

Query:

[10:15, 11:00]

The overlapping results are:

Design review:  [09:30, 11:30]
Customer call:  [10:45, 11:15]

The team meeting ends before the query begins. Lunch and the planning session begin after the query ends. A tree query can report the two relevant events while pruning portions of the structure that cannot contain a result.

9. Maintaining Summaries During Updates​

Insertion has two responsibilities:

1. Place the interval according to the ordering rule.
2. Repair maxEnd on every affected ancestor.

A common error is to perform the first step but forget the second. The tree may still appear correctly ordered, yet its query decisions can be wrong because an ancestor has a stale summary.

Suppose a node currently has:

node.interval.end = 10:00
left.maxEnd = 09:30
right.maxEnd = 12:00

Its correct maxEnd is 12:00. If a new interval ending at 13:00 is inserted into the left subtree, the insertion path must be updated all the way to the root. The affected nodes may now have maxEnd = 13:00.

Recomputing from the formula is safer than trying to update values with ad hoc increments. At every affected node, calculate the maximum of the node's own endpoint and its current child summaries. This approach continues to work when the tree later supports deletion or changes to existing intervals.

The summary is a derived value. It should always be possible to recompute it from the actual subtree.

10. Deletion and Editing Calendar Events​

Removing an event can reduce the maximum endpoint in one or more subtrees. For example, consider a subtree containing:

[09:00, 10:00]
[09:30, 13:00]
[11:00, 12:00]

The subtree's maxEnd is 13:00. If [09:30, 13:00] is deleted, the correct summary becomes 12:00.

A stale value that is too large may not immediately produce a false overlap, but it prevents effective pruning. The tree will behave as though a later-ending interval might still exist. More importantly, stale derived data violates the invariant and can make future updates difficult to reason about.

A summary that is too small is more dangerous. It can cause the query to skip a subtree that actually contains a valid match. Therefore, after deleting a node or replacing a child pointer, recompute maxEnd for the affected node and each ancestor on the path to the root.

An edited calendar event can be handled conceptually as:

1. Delete the old interval.
2. Insert the updated interval.

A specialized update can also be used, but the delete-and-insert model is straightforward and makes it clear that both the ordering and summary values must be restored.

11. Tree Shape and Balancing Considerations​

The maxEnd augmentation does not automatically balance the underlying search tree. If intervals are inserted in increasing start order into an ordinary binary search tree, the result can become a chain:

[09:00, 10:00]
                  \
                 [10:00, 11:00]
                                  \
                                 [11:00, 12:00]

The maxEnd values may still be completely correct, but the tree has little branching structure. A search can then follow a long path instead of benefiting from a compact hierarchy.

This gives two separate design concerns:

• The tree shape affects path length and practical search behavior.
• The maxEnd invariant determines whether interval-based pruning is correct.

If the implementation uses a balanced tree, rotations may change child relationships. After a rotation, recompute the summaries of the nodes whose children changed. The lower node is generally updated before its new parent because the parent's summary depends on the lower node's corrected value.

Whether a balancing strategy is used depends on the implementation and workload. The interval-tree technique itself is the combination of ordering by an interval endpoint and maintaining a subtree maximum endpoint.

12. Endpoint Semantics for Calendars​

Calendar applications frequently use half-open intervals because they represent adjacent events naturally. With [start, end) semantics:

[09:00, 10:00)
[10:00, 11:00)

The events do not overlap. The first event finishes exactly when the second begins.

With closed intervals, the overlap predicate is commonly:

first.start <= second.end and second.start <= first.end

With half-open intervals, it is commonly:

first.start < second.end and second.start < first.end

The same decision must influence pruning. If a query begins exactly when a subtree's maximum end occurs, the implementation must know whether that equality keeps the subtree relevant. A mismatch between the overlap function and the pruning condition can create boundary bugs.

A practical implementation should define one clearly named overlap function and use it consistently. Tests should include:

• intervals separated by a gap;
• intervals that touch at one endpoint;
• one interval contained inside another;
• identical intervals;
• a query that begins exactly when a stored interval ends;
• a query that ends exactly when a stored interval begins.

These cases are especially valuable because ordinary examples often do not expose equality mistakes.

13. Complexity and Work Performed by a Query​

The benefit of an interval tree comes from avoiding unnecessary interval comparisons. Its actual performance depends on:

• the shape of the underlying tree;
• the number of intervals that overlap the query;
• the number of subtrees that remain possible;
• whether the query stops after one result or reports all results;
• whether the tree is balanced or skewed.

A one-overlap query can stop immediately after finding a qualifying event. An all-overlaps query must continue through every relevant region, and a query with many matches naturally requires more work because those results must be reported.

The maxEnd value enables subtree-level rejection, but it does not guarantee that every query visits only a very small number of nodes. If intervals overlap heavily, many branches may remain relevant. If the tree is badly skewed, paths may be long. “Efficient” therefore means that the data structure has information that supports pruning; the exact amount of work depends on the tree and the interval distribution.

When evaluating an implementation, consider both the expected tree shape and the expected overlap pattern. A calendar with many dense, overlapping events presents a different workload from a calendar whose events are widely separated.

14. A Minimal Data Model​

A conceptual interval-tree node can be represented as:

Node:
    start
    end
    maxEnd
    left
    right

A calendar application can attach additional information such as an event identifier, title, room, or attendee list:

Event:
    id = "design-review"
    start = 09:30
    end = 11:30

Tree node:
    interval = Event
    maxEnd = 11:30

The additional event fields are application data. The interval tree uses the start and end values to organize and query the records, and uses maxEnd to summarize the subtree.

Equal start values require a defined policy. The implementation might compare (start, end) pairs, place equal-start intervals consistently on one side, or store several events under one start key. Any of these approaches can work if the ordering policy is deterministic and is applied during every operation.

15. Common Implementation Mistakes​

Forgetting to update ancestors​

If a newly inserted interval has the largest endpoint in the tree, its own maxEnd is not enough. The value must propagate to every affected ancestor. Otherwise, a query may incorrectly prune the path containing the new interval.

Inspecting the wrong summary​

When deciding whether the left subtree is worth searching, inspect the left child's maxEnd. The current node's summary includes both subtrees and the current interval, so it cannot specifically certify that the left subtree is relevant.

Treating a possible match as a definite match​

A subtree with a sufficiently large maxEnd may contain an overlap, but the summary alone does not prove that it does. The actual interval at each visited node must still be checked.

Mixing endpoint conventions​

A closed-interval overlap test combined with half-open pruning rules can produce errors when intervals touch. Choose a convention and use it in both overlap and traversal logic.

Ignoring duplicate starts​

Equal start times need deterministic handling. Without a tie-breaking rule, the ordering invariant becomes ambiguous and search behavior may not be repeatable.

Allowing stale large summaries​

A summary that is too large may mainly reduce pruning, but it still violates the data structure's invariant. It can also complicate deletion and validation. Recompute summaries from the actual children after changes.

Assuming the tree balances itself​

The interval-tree summary does not balance the tree. Insertion order can create a skewed structure unless the underlying implementation provides a balancing mechanism.

16. Validating the Structure​

A useful validation routine recursively recomputes the expected maximum endpoint for each subtree and compares it with the stored value:

validate(node):
    if node is empty:
        return the identity value for maximum

    leftMax = validate(node.left)
    rightMax = validate(node.right)
    expected = max(node.end, leftMax, rightMax)

    assert node.maxEnd == expected
    return expected

The identity value depends on the endpoint type. Numeric endpoints can use a suitably small value. Time objects need a representation that supports the required comparisons.

Validation should also check ordering. Every interval in the left subtree must satisfy the left-side ordering relation, and every interval in the right subtree must satisfy the right-side relation. Equal-start behavior must be included in this check.

For query testing, compare the tree against a simple list scan. The list scan is easy to understand and can serve as a reference for small test data. Insert a collection of calendar intervals, run a query through both implementations, and compare the returned sets. This helps reveal both missed matches and incorrect boundary handling.

Important test cases include:

1. An empty tree.
2. A tree containing one interval.
3. A query overlapping the root.
4. A query overlapping only a deep interval.
5. A query with no overlap.
6. A query touching an endpoint.
7. Nested intervals.
8. Multiple intervals with identical starts.
9. Inserting a new maximum endpoint.
10. Deleting the interval that supplies a subtree maximum.

The validator is particularly useful after insertion, deletion, and any operation that changes child pointers.

17. A Practical Calendar Workflow​

A calendar application can use an interval tree through the following workflow:

1. Convert each event into a consistent interval representation.
2. Insert the event using its start as the primary ordering key.
3. Maintain maxEnd while returning from the insertion path.
4. Query the tree with a proposed event interval.
5. Use the returned event or events to identify conflicts.
6. Delete and reinsert an event when it is removed or edited, or use an equivalent update that restores both invariants.

A conflict check may stop after finding the first overlap. A conflict report may collect every overlap. Both operations use the same tree and differ mainly in whether the traversal stops after one result.

The interval tree answers a structural question: which stored intervals overlap this query interval? It does not decide what a calendar should do with the conflict. Application rules may determine whether a conflict is allowed, whether a room is available, or whether a user should be warned. Those policies are separate from the tree's organization and search logic.

The same structure can also support associated records. Once an overlapping node is found, the application can return the event identifier and other metadata stored with that interval.

18. Practical Takeaways​

An interval tree combines an ordered search tree with a subtree maximum. The essential design is concise:

• Store each interval's start and end.
• Order nodes by start, with a clear policy for equal starts.
• Store maxEnd at every node.
• Define maxEnd as the maximum end anywhere in the node's subtree.
• Recompute summaries after insertions, deletions, rotations, and edits.
• Test each visited interval with the chosen overlap predicate.
• Skip a subtree when its maximum end proves that all intervals end before the query begins.
• Use start ordering to avoid intervals that begin after the query ends.
• Keep endpoint semantics consistent in every comparison.
• Consider tree shape, overlap density, and output size when evaluating performance.

The most important invariant is:

node.maxEnd = maximum end value anywhere in node's subtree

The most important pruning insight is:

if subtree.maxEnd is before the query start,
then that entire subtree cannot overlap the query

Together, these ideas allow the data structure to reason about groups of calendar events instead of treating every event as an unrelated record. Construction establishes the ordering and summaries. Insertions and deletions preserve them. Queries use them to find possible conflicts and discard impossible regions. That combination is the foundation of interval-tree-based overlap management.