Interval Tree vs Sorted List for Seasonal Rate Lookup

Every priced meter read starts with one question: which seasonal period was in force at that instant? For a municipal schedule of a handful of non-overlapping seasons the answer feels trivial, but the lookup runs once per read and a monthly cycle carries millions of reads, so the data structure behind it decides whether resolution is a rounding error or a bottleneck. The two credible choices are a sorted list of period boundaries searched with bisect and a purpose-built interval tree. This page sits under seasonal rate mapping and calendar logic, part of the broader automated rate calculation and rule engines subsystem, and works through which structure fits which schedule — with a runnable implementation of both and a clear recommendation for the typical case.

The distinction that governs the choice is whether periods can overlap. A sorted boundary list assumes the schedule partitions time: consecutive, non-overlapping, gap-free half-open intervals where exactly one period covers any instant. An interval tree makes no such assumption — it returns all intervals that contain a point, which is precisely what you need when drought surcharges, peak-demand windows, and base seasons layer over the same calendar and a read can legitimately match several at once.

# Minimal Prerequisites

• Python 3.11+ — for zoneinfo and modern typing; the standard-library bisect module supplies the sorted-list search with no dependency.
• decimal.Decimal for every tier price. The lookup structure never touches money, but the periods it stores carry Decimal rates that must survive the round trip untouched.
• Timezone-aware datetime bounds. Both structures compare instants; a naive datetime silently floats the boundary by the UTC offset. Periods are assumed already validated as half-open [start, end) intervals, as modeled in the parent cluster.
• Data assumption: for the sorted list, periods are non-overlapping and pre-sorted by start; for the tree, periods may overlap freely. Both assume bounds are comparable datetime objects in a single reference frame (compare in UTC internally).

# The comparison at a glance

Both share the same asymptotic lookup class for a single hit, so the decision is rarely about raw speed on small schedules. It is about semantics: the sorted list is a total function returning one period, the tree is a set-valued function returning zero or more. Reach for the structure whose return shape matches your pricing model, not the one with the fancier name.

# Annotated Implementation

Below are both approaches against the same period model. The sorted list keeps a parallel array of start boundaries and uses bisect_right to find the rightmost period whose start is at or before the read, then confirms containment. The interval tree is a compact augmented binary search tree over start times, where each node caches the maximum end in its subtree so whole branches that cannot contain the query point are pruned.

from __future__ import annotations

from bisect import bisect_right
from dataclasses import dataclass, field
from datetime import datetime
from decimal import Decimal


@dataclass(frozen=True)
class Period:
    period_id: str
    start: datetime          # inclusive lower bound, tz-aware
    end: datetime            # exclusive upper bound, tz-aware
    rate: Decimal            # price per unit; Decimal, never float

    def contains(self, when: datetime) -> bool:
        # Half-open [start, end): a boundary instant belongs to exactly one period.
        return self.start <= when < self.end


# ---- Approach A: sorted list + bisect (one covering period) -----------------

class SortedPeriodIndex:
    """Assumes non-overlapping periods that partition the timeline."""

    def __init__(self, periods: list[Period]) -> None:
        # Sort once at build; store a parallel key array for bisect.
        self._periods = sorted(periods, key=lambda p: p.start)
        self._starts = [p.start for p in self._periods]

    def resolve(self, when: datetime) -> Period | None:
        # Rightmost period whose start <= when, then verify the end bound.
        idx = bisect_right(self._starts, when) - 1
        if idx >= 0 and self._periods[idx].contains(when):
            return self._periods[idx]
        return None  # calendar gap — caller diverts, never guesses


# ---- Approach B: interval tree (all covering periods) -----------------------

@dataclass
class _Node:
    period: Period
    max_end: datetime                       # max end across this subtree
    left: "_Node | None" = None
    right: "_Node | None" = None


class IntervalTree:
    """Returns every period covering an instant — supports overlaps."""

    def __init__(self, periods: list[Period]) -> None:
        ordered = sorted(periods, key=lambda p: p.start)
        self._root = self._build(ordered, 0, len(ordered) - 1)

    def _build(self, items: list[Period], lo: int, hi: int) -> _Node | None:
        # Balanced by construction: pick the median start as the subtree root.
        if lo > hi:
            return None
        mid = (lo + hi) // 2
        node = _Node(period=items[mid], max_end=items[mid].end)
        node.left = self._build(items, lo, mid - 1)
        node.right = self._build(items, mid + 1, hi)
        # Augment: cache the largest end below this node for pruning.
        for child in (node.left, node.right):
            if child is not None and child.max_end > node.max_end:
                node.max_end = child.max_end
        return node

    def resolve_all(self, when: datetime) -> list[Period]:
        matches: list[Period] = []
        self._search(self._root, when, matches)
        return matches

    def _search(self, node: _Node | None, when: datetime, out: list[Period]) -> None:
        if node is None or when >= node.max_end:
            return  # nothing in this subtree can start-and-end around `when`
        self._search(node.left, when, out)
        if node.period.contains(when):
            out.append(node.period)
        if when >= node.period.start:  # only the right subtree can still match
            self._search(node.right, when, out)

The max_end augmentation is the whole trick of the tree. Because every node knows the latest end anywhere beneath it, the search abandons a subtree the moment the query instant lands at or past that maximum — no interval down there can still contain it. That pruning is what turns a walk of the whole tree into an O(log n + k) visit that touches only the branches capable of matching, where k is the number of overlapping periods actually returned. The sorted list needs no such machinery precisely because its contract forbids overlaps: once bisect_right finds the candidate, at most one period can contain the instant, so a single contains check settles it.

# Edge Cases and Billing Gotchas

The structures behave identically on the happy path and diverge exactly where municipal calendars get messy. These are the cases that decide the choice.

• Overlapping periods. If two periods genuinely cover the same instant — a base summer season and a drought surcharge window layered on top — the sorted list is the wrong tool: bisect returns one and silently drops the other, underbilling the surcharge. The interval tree returns both, and pricing layers them per the surcharge and fee application sequence. If your periods never overlap, this cannot bite and the sorted list is simpler and safer.
• Boundary instants. A read at exactly Oct 1 00:00:00 must belong to precisely one base period. Both structures rely on half-open [start, end) containment so the boundary is single-valued; if you accidentally store inclusive-inclusive bounds, the tree will return two base periods and the sorted list will pick whichever sorts first — both wrong. Enforce half-open bounds at validation, before either structure is built.
• Daylight saving transitions. Neither structure resolves DST for you. Both compare raw instants, so the correctness of the answer depends entirely on the bounds and the query being in the same reference frame — compare in UTC internally. The civil-time-to-instant conversion is a separate concern handled in computing seasonal rate boundaries across DST transitions; build either structure only after that conversion is done.
• Open-ended final period. The current season often has no defined end (“summer rate, until further notice”). Model it with a sentinel far-future end (e.g. datetime.max made tz-aware) rather than None, so contains and the tree’s max_end comparison stay total. A None end forces branchy special-casing that defeats the O(log n) search and invites a TypeError at the first comparison.
• Rebuild versus mutate. A retroactive schedule change should rebuild the structure from the append-only period store, never mutate nodes in place. Both classes are cheap to reconstruct at O(n log n); an in-place edit risks leaving a stale max_end cached in the tree and a desynced _starts array in the list, producing lookups that are wrong in ways no unit test on the new schedule will catch.

# Verification Snippet

Prove the two structures agree on a non-overlapping schedule, and that the tree alone captures a deliberate overlap the list cannot represent.

from datetime import datetime, timezone
from decimal import Decimal


def _p(pid: str, s: str, e: str, rate: str) -> Period:
    fmt = "%Y-%m-%d"
    return Period(
        period_id=pid,
        start=datetime.strptime(s, fmt).replace(tzinfo=timezone.utc),
        end=datetime.strptime(e, fmt).replace(tzinfo=timezone.utc),
        rate=Decimal(rate),
    )


def test_structures_agree_on_non_overlapping_schedule() -> None:
    seasons = [
        _p("winter", "2026-01-01", "2026-06-01", "0.0098"),
        _p("summer", "2026-06-01", "2026-10-01", "0.0142"),
        _p("fall", "2026-10-01", "2027-01-01", "0.0110"),
    ]
    sl = SortedPeriodIndex(seasons)
    it = IntervalTree(seasons)
    when = datetime(2026, 10, 1, tzinfo=timezone.utc)  # boundary instant

    one = sl.resolve(when)
    many = it.resolve_all(when)
    assert one is not None and one.period_id == "fall"     # half-open: fall, not summer
    assert [p.period_id for p in many] == ["fall"]          # tree agrees: single match


def test_tree_captures_overlap_the_list_drops() -> None:
    layered = [
        _p("summer-base", "2026-06-01", "2026-10-01", "0.0142"),
        _p("drought", "2026-07-01", "2026-09-01", "0.0025"),  # overlaps summer
    ]
    when = datetime(2026, 7, 15, tzinfo=timezone.utc)
    matched = {p.period_id for p in IntervalTree(layered).resolve_all(when)}
    assert matched == {"summer-base", "drought"}             # both returned

    dropped = SortedPeriodIndex(layered).resolve(when)
    assert dropped is not None and dropped.period_id == "drought"  # list keeps only one

The second test is the honest one: it shows the sorted list is not merely slower on overlaps, it is wrong — it returns a single period and silently discards the surcharge. That is the failure mode the comparison table’s “handles overlaps” column is really about.

# Recommendation

For the overwhelming majority of municipal seasonal schedules — a small, fixed set of non-overlapping seasons that partition the year — use the sorted list with bisect. It is a dozen lines, has no dependency beyond the standard library, resolves in O(log n), and its return type (exactly one period, or a gap you divert) matches the pricing model directly. The interval tree earns its extra complexity only when periods genuinely overlap and you need every covering interval in one query, or when a single schedule carries hundreds of layered, arbitrarily nested windows. Do not reach for the tree on the theory that you might need overlaps later: model overlapping surcharges as a separate layer resolved on top of the base-season lookup, keep the base resolution on the sorted list, and reconstruct either structure from the append-only store whenever the schedule changes.

# FAQ

# Related Topics

• Seasonal Rate Mapping & Calendar Logic — the parent guide covering timezone-aware period resolution end to end.
• Computing Seasonal Rate Boundaries Across DST Transitions — converting civil season boundaries to the instants these structures compare against.
• Automated Rate Calculation & Rule Engines — the subsystem this lookup feeds.
• Surcharge & Fee Application Logic — layering overlapping surcharges the interval tree returns together.
• Proration & Billing Period Calculation — splitting a cycle once the covering periods are resolved.

Up: Seasonal Rate Mapping & Calendar Logic · Automated Rate Calculation & Rule Engines