Intervals

Interval problems are decided at the boundaries. This guide starts with the convention question — half-open against closed, and whether touching intervals conflict — because nearly every defect in this area is an off-by-one traceable to it. It then covers merging and insertion, the sweep-line reduction that turns interval questions into a pass over a running counter, the min-heap of end times that yields resource assignment rather than just peak concurrency, and the greedy selection by earliest finish. The later sections move to structures that support updates — interval trees, segment trees with lazy propagation, and Fenwick trees with their invertibility requirement — and to the real-world complications of calendar arithmetic and floating-point endpoints.

half-open interval conventions

Whether an interval includes its endpoints must be fixed before any algorithm is written, and half-open is almost always the better choice.

With half-open intervals, adjacent ranges touch without overlapping, lengths subtract cleanly, and no special case is needed for zero-length ranges.

Adjacent half-open ranges touch without overlapping; lengths subtract cleanly.

# Half-open [start, end): [0, 10) and [10, 20) are adjacent, not overlapping.
length = end - start                     # 10, no +1 anywhere
# Closed [start, end]: [0, 10] and [10, 20] share the point 10.
length = end - start + 1                 # the +1 that goes missing

Interview trap. Mixing closed and half-open conventions in one codebase produces off-by-one errors in overlap tests that look like data problems.

Engineering practice. Adopt half-open throughout, document it once, and convert at the boundary when an external format is closed.

the overlap test

Two intervals overlap exactly when each starts before the other ends, which is a two-comparison test rather than a case analysis.

Under a half-open convention the test uses strict inequality on one side, and under a closed convention both sides are non-strict.

Two comparisons, not four cases.

def overlaps(a, b):                      # half-open
    return a[0] < b[1] and b[0] < a[1]

overlaps((0, 10), (10, 20))   # False - adjacent
overlaps((0, 10), (9, 20))    # True

Interview trap. Enumerating the containment and partial-overlap cases separately produces four branches, one of which is usually wrong.

Engineering practice. Use the two-comparison form, and derive the strictness from the interval convention in force.

sorting by start time

Merging overlapping intervals requires sorting by start time, after which one linear pass suffices.

Sorted by start, each interval either extends the current merged range or begins a new one, and no earlier interval can reopen a closed range.

Merging needs start order; selection needs end order.

intervals.sort(key=lambda x: x[0])       # merging
intervals.sort(key=lambda x: x[1])       # maximum non-overlapping selection

Interview trap. Sorting by end time makes merging incorrect, because a later-starting interval can then arrive before one it overlaps.

Engineering practice. Sort by start for merging and by end for selection, and say which problem is being solved.

merging overlapping intervals

The merge pass extends the current interval's end when the next interval starts before it, and emits otherwise.

The extension takes the maximum of the two ends, because the next interval may be entirely contained within the current one.

Take the maximum end; containment breaks assignment.

out = []
for s, e in sorted(intervals):
    if out and s < out[-1][1]: out[-1][1] = max(out[-1][1], e)    # half-open: touching is separate
    else: out.append([s, e])

# [(1, 10), (2, 3)] -> [(1, 10)]. Assigning e gives [(1, 3)].

Interview trap. Assigning the next interval's end rather than taking the maximum shrinks the merged range whenever containment occurs.

Engineering practice. Take the maximum on extension, and test with a long interval followed by a short contained one.

inserting into a sorted interval list

Inserting one interval into a disjoint sorted list has three phases: intervals entirely before, intervals overlapping, and intervals entirely after.

The overlapping run is absorbed into a single interval spanning the minimum start and maximum end, and the rest are copied unchanged.

Three phases: before, overlapping, after.

i, out = 0, []
while i < len(iv) and iv[i][1] <= new[0]: out.append(iv[i]); i += 1    # before
while i < len(iv) and iv[i][0] < new[1]:
    new = [min(new[0], iv[i][0]), max(new[1], iv[i][1])]; i += 1       # absorb
out.append(new); out.extend(iv[i:])                                    # after

Interview trap. Handling the merge with a general re-merge of the whole list is correct but linearithmic where the three-phase pass is linear.

Engineering practice. Write the three phases explicitly, and test insertions before all, after all, and spanning every existing interval.

the sweep-line technique

Converting intervals into start and end events and sorting them turns many interval problems into a single pass over a running counter.

A start event increments the count and an end event decrements it, so the maximum count is the peak overlap.

Order the tie deliberately; touching intervals depend on it.

events = []
for s, e in iv:
    events.append((s, +1)); events.append((e, -1))
events.sort()          # (10, -1) sorts before (10, +1): touching does not overlap

Interview trap. Ordering start and end events at the same coordinate incorrectly changes the answer for touching intervals by one.

Engineering practice. Define the tie-breaking rule from the interval convention, and test intervals that touch exactly at a boundary.

meeting rooms and peak concurrency

The minimum number of resources for a set of intervals equals the maximum number overlapping at any point.

Either a sweep over events or a min-heap of end times computes it, and the heap version additionally yields the assignment.

Rooms equal the maximum simultaneous overlap.

# [(0,30), (5,10), (15,20)] -> peak 2, so 2 rooms.
# Total duration is 40 minutes, which says nothing about the answer.

Interview trap. Assuming the answer relates to the total duration or the interval count rather than the peak gives an unrelated number.

Engineering practice. Compute peak concurrency, and use the heap when the specific assignment is needed rather than just the count.

the min-heap of end times

Processing intervals in start order while keeping active end times in a min-heap gives resource assignment in linearithmic time.

Before assigning a new interval, every heap entry whose end is at or before the new start is popped, freeing those resources.

Pop every expired end, not just one.

import heapq
h = []
rooms = 0
for s, e in sorted(iv):
    while h and h[0] <= s: heapq.heappop(h)     # a while, not an if
    heapq.heappush(h, e)
    rooms = max(rooms, len(h))                   # peak, not the final active count

Interview trap. Popping only one expired entry per iteration leaves stale resources allocated and overstates the requirement.

Engineering practice. Pop in a loop until the heap top is genuinely active, and test with many short intervals followed by one long one.

non-overlapping selection

Selecting the most non-overlapping intervals is greedy by earliest end time, and removing the fewest intervals is its complement.

The two problems have the same answer expressed differently, so an implementation of one solves the other by subtraction.

Maximum kept and minimum removed are the same computation.

kept = greedy_by_end(iv)
removed = len(iv) - kept

Interview trap. Sorting by start time or by duration for this problem fails, and each has a three-interval counterexample.

Engineering practice. Sort by end time, and be ready to state the exchange argument and the counterexamples to the alternatives.

interval intersection of two lists

Intersecting two sorted disjoint interval lists is a two-pointer merge in linear time.

The intersection of the current pair is the later start to the earlier end, and the pointer whose interval ends first advances.

Advance the pointer whose interval ends first.

i = j = 0
while i < len(a) and j < len(b):
    lo, hi = max(a[i][0], b[j][0]), min(a[i][1], b[j][1])
    if lo < hi: out.append((lo, hi))
    if a[i][1] < b[j][1]: i += 1
    else: j += 1

Interview trap. Advancing both pointers after emitting an intersection skips intervals that could still intersect the other list.

Engineering practice. Advance only the pointer with the earlier end, and emit only when the computed intersection is non-empty.

interval subtraction and gaps

Finding the gaps in a set of intervals is merging followed by taking the complement between consecutive merged ranges.

The complement also requires an explicit universe range, because the gaps before the first and after the last interval depend on it.

Gaps need an explicit universe, or the ends are lost.

def gaps(merged, lo, hi):
    out, cur = [], lo
    for s, e in merged:
        if cur < s: out.append((cur, s))
        cur = max(cur, e)
    if cur < hi: out.append((cur, hi))     # the trailing gap
    return out

Interview trap. Omitting the universe bounds silently drops the leading and trailing gaps, which are often the ones that matter.

Engineering practice. Take the universe as an explicit parameter, and test with intervals that do not reach either bound.

employee free time

Finding the intervals free across several schedules is merging all intervals from all sources and reporting the gaps.

The identity of the source is irrelevant to the answer, which is why the lists can be concatenated before merging.

Concatenate, merge once, report the gaps.

free = gaps(merge(sorted(chain.from_iterable(schedules))), lo, hi)

Pairwise intersection across k schedules is O(k^2); this is one O(n log n) sort.

Interview trap. Intersecting the free time of each schedule pairwise is correct but quadratic in the number of schedules.

Engineering practice. Concatenate, merge once, and report the gaps, quoting the linearithmic bound from the single sort.

counting overlaps at query points

Answering many 'how many intervals cover this point' queries is done with a difference array or prefix sums rather than per-query scanning.

Each interval increments at its start and decrements at its end, and the prefix sum of the difference array gives the coverage at every point.

A difference array, then a prefix sum.

diff = [0] * (maxt + 2)
for s, e in iv: diff[s] += 1; diff[e] -= 1      # half-open: decrement at e, not e+1
coverage = list(accumulate(diff))

Interview trap. The decrement position depends on the interval convention, and getting it wrong shifts every count by one at the boundaries.

Engineering practice. Derive the decrement index from the convention, and validate against a direct count on small inputs.

coordinate compression

When interval endpoints are large or sparse, mapping them to consecutive indices makes array-based techniques usable.

Sorting the distinct endpoints and replacing each value by its rank preserves all order relationships, which is all these algorithms depend on.

Rank the distinct endpoints, and keep both mappings.

points = sorted({p for s, e in iv for p in (s, e)})
index = {p: i for i, p in enumerate(points)}
# Endpoints up to 10^9 compress to at most 2n indices, and points[i] recovers the value.

Interview trap. Compressing endpoints without keeping the segment lengths loses the ability to report any answer measured in original units.

Engineering practice. Keep the mapping both ways, and carry segment lengths when the answer is a measure rather than a count.

interval trees

An interval tree answers 'which stored intervals overlap this query' in time proportional to the logarithm plus the number of results.

It augments a balanced binary search tree over start points with the maximum end in each subtree, which prunes subtrees that cannot overlap.

Augment with the subtree maximum end, and update it on every rotation.

node.max_end = max(node.end, node.left.max_end, node.right.max_end)
# Query: if node.left and node.left.max_end > q.start, the left subtree may overlap.

Interview trap. Failing to update the augmented maximum on rotation leaves the pruning rule wrong and the query silently incomplete.

Engineering practice. Update augmentation inside the rebalancing code, and assert query results against a linear scan in tests.

segment trees

A segment tree supports range aggregate queries and point or range updates in logarithmic time.

Each node stores an aggregate over a fixed range, and a query decomposes into a logarithmic number of nodes covering the requested range.

Use one only when the data changes between queries.

Data	Queries	Structure
static	many range sums	prefix-sum array, O(1)
point updates	range sums	Fenwick tree, O(log n)
range updates	range sums	segment tree with lazy propagation

Interview trap. Using a segment tree where a prefix-sum array suffices adds substantial complexity for no benefit when there are no updates.

Engineering practice. Use prefix sums for static data, and a segment tree only when the data changes between queries.

lazy propagation

Range updates on a segment tree require deferring the update to children until they are visited.

A pending update is stored at the covering node and pushed down on the next descent, which keeps range updates logarithmic.

Push down on descent; applying eagerly makes range updates linear.

def push(node):
    if lazy[node]:
        for child in (2*node, 2*node+1):
            tree[child] += lazy[node] * span[child]; lazy[child] += lazy[node]
        lazy[node] = 0

Interview trap. Applying updates eagerly to every covered leaf makes a range update linear and defeats the structure.

Engineering practice. Implement push-down at the start of every descent, and test interleaved range updates and queries against a naive array.

binary indexed trees

A Fenwick tree gives prefix aggregates with point updates in logarithmic time and far less code and memory than a segment tree.

It exploits the binary representation of indices to store partial aggregates; arbitrary point updates plus range queries work cleanly for invertible aggregates such as sums.

Sums yes, maxima no - the aggregate must be invertible.

def update(i, delta):
    while i <= n: bit[i] += delta; i += i & -i
def prefix(i):
    s = 0
    while i > 0: s += bit[i]; i -= i & -i
    return s

A maximum cannot be undone when a value decreases, so a Fenwick tree cannot hold one.

Interview trap. Attempting to store a maximum in a Fenwick tree fails for arbitrary updates, because a maximum cannot be undone.

Engineering practice. Use it for sums and counts, and reach for a segment tree when the aggregate has no inverse.

the boundary condition in tie-breaking

Whether intervals that touch at an endpoint count as overlapping is a domain decision, not a technical one.

A meeting ending at ten and one starting at ten do not conflict; a closed numeric range containing ten twice is a duplicate.

A domain question, not a technical one.

# Meetings: 09:00-10:00 and 10:00-11:00 do not conflict -> half-open.
# Sensor readings sampled at t: [0, 10] and [10, 20] share the sample at 10 -> closed.

Interview trap. Choosing the convention from the algorithm's convenience rather than from the domain produces answers that are wrong by exactly one in the boundary case.

Engineering practice. Ask the domain question first, encode the answer in the comparison, and test the touching case explicitly.

intervals over time zones and calendars

Real scheduling intervals live on a calendar, where arithmetic is not uniform and instants are not interchangeable with local times.

Daylight-saving transitions make some local times ambiguous or absent, so intervals must be stored as instants and rendered in a zone.

Store instants; render in a zone.

from datetime import datetime
from zoneinfo import ZoneInfo
# 2026-03-29 01:30 in Europe/London does not exist when clocks jump to 02:00.
# 2026-10-25 01:30 exists twice - the same wall clock, two different instants.

Comparing wall-clock strings across the transition produces overlaps that are wrong.

Interview trap. Storing local wall-clock times and comparing them directly produces overlaps that are wrong across a transition.

Engineering practice. Store instants in a fixed reference, convert only for display, and test across a daylight-saving boundary.

floating-point endpoints

Interval endpoints in floating point make exact boundary comparisons unreliable.

Values that should be equal after arithmetic often differ in the last bits, so a strict comparison classifies touching intervals inconsistently.

Values that should be equal often are not.

0.1 + 0.2 == 0.3          # False
(0.1 + 0.2) - 0.3         # 5.55e-17 - enough to flip a strict comparison

Use integers or a fixed-point representation for endpoints where the boundary matters.

Interview trap. Adding an epsilon to the comparison changes the answer for genuinely tiny intervals and is not a general fix.

Engineering practice. Use exact integer or fixed-point representations for endpoints where possible, and state the tolerance explicitly when they must be floating point.

very large interval sets

When intervals do not fit in memory, the sweep becomes an external sort followed by a streaming pass.

The sweep only needs the events in order and a bounded active set, both of which stream well.

Sort-then-stream ports to an external sort unchanged.

# 10^9 intervals: the sweep needs the events in order and a bounded active set.
# Both stream, so the in-memory sort is the only part that has to change.

Interview trap. Assuming an in-memory sort is available is the assumption that fails first at scale, before the algorithm itself does.

Engineering practice. Structure interval processing as sort-then-stream so it ports to an external or distributed sort unchanged.

rate limiting as an interval problem

A sliding-window rate limiter is a coverage query over intervals of recent requests.

Counting requests in the last window is exactly a range count, which a ring buffer or a counter per bucket answers in constant time.

Bucketed counters bound memory and state the error.

# Exact log of every attempt: unbounded under rejected load, which is when it matters.
# Bucketed: 60 one-second counters, error at most one bucket boundary.
allowed = sum(buckets) < limit

Interview trap. Storing every attempted request timestamp gives exact answers with unbounded memory under rejected load, which is when the limiter matters most.

Engineering practice. Use bucketed counters with a bounded error, and state the error the approximation introduces.

testing interval code

Interval defects live at the boundaries, so tests must include touching, nested, identical, and zero-length intervals.

These four shapes exercise every branch of the overlap test and the merge extension, which random intervals rarely do.

Touching, nested, identical and zero-length are the four shapes.

cases = [((0, 10), (10, 20)),   # touching
         ((0, 10), (2, 3)),     # nested
         ((0, 10), (0, 10)),    # identical
         ((5, 5),  (0, 10))]    # zero length

Interview trap. Testing only with clearly separated or clearly overlapping intervals passes almost every incorrect implementation.

Engineering practice. Include the four boundary shapes in every suite, and compare merged output against a brute-force point-coverage computation.

choosing the technique

Static interval sets are handled by sorting and sweeping; changing sets need a tree structure.

Sorting plus a sweep is linearithmic once and linear thereafter; an interval or segment tree pays a logarithmic factor per operation to allow updates.

Update frequency decides it.

Workload	Approach
Static set, many queries	sort once, then sweep or binary search
Frequent inserts and deletes	interval tree
Range updates and range queries	segment tree with lazy propagation
Point updates, prefix sums	Fenwick tree

Interview trap. Rebuilding the sorted structure after each update converts a logarithmic operation into a linearithmic one repeated per change.

Engineering practice. Choose from the update frequency, and say what the structure gives up when the simpler approach is chosen.