Skip to content
Hari KharelStudy

Intervals

coreCommon atGoogleMetaStripeAmazonRead firstSorting and comparatorsTwo pointersPractise in the Sandbox →

An interval is a pair [start, end]. Two intervals overlap exactly when max(starts) ≤ min(ends) (strict < for half-open ranges). Sort by start, and anything that overlaps the current group must start before the group ends, so one pass after an O(n log n) sort handles merging, conflict checks and gaps.

The idea in plain words

Section titled “The idea in plain words”

Think of a wall calendar. Meetings are coloured bars. If you shuffle the bars, spotting clashes means comparing every pair: O(n²). Line them up by start time and something useful happens: a bar can only clash with the bars just before it that haven’t ended yet.

So the whole topic rests on two small facts:

  • The overlap test. The later start must come no later than the earlier end. Everything else (containment, partial overlap, identical ranges) is a special case of that one line.
  • Sorting by start. Once sorted, you carry a tiny summary of “what’s open” (the end of the current merged block, or the latest end seen) and look at each interval once.

The real trap is not the algorithm. It’s the endpoint convention: does [1, 3] overlap [3, 5]? With closed ranges (both ends included) yes, they share the point 3. With half-open ranges [1, 3) (end excluded, the usual choice for time) no, one ends exactly as the next starts.

See it

Section titled “See it”

Edit the intervals, flip the endpoint rule, and step through. Watch the “open” block on the output lane: it only ever grows rightward or gets emitted.

Merge overlapping intervals
step through
[8,10][1,3][15,18][2,6][10,12][17,20][4,5]output01234567891011121314151617181920
merged0
current intervalin the open blockopen blockemitted
Input in arbitrary order. Overlap is only easy to check between neighbours, so first sort by start.
1 / 12

Drag the sliders to try every arrangement of two intervals. One formula covers all six cases.

The overlap test: max(starts) vs min(ends)
drag the sliders
ABA ∩ B012345678910111213141516
lomax(2, 7) = 7
himin(7, 12) = 7
overlapyes
They overlap on [7, 7]. The later start comes no later than the earlier end.

When to reach for it

Section titled “When to reach for it”
The problem says… Why intervals fit
“meetings”, “bookings”, “reservations”, “shifts” Each is a [start, end] on a time line.
“merge”, “union”, “combine overlapping ranges” Sort by start, extend or emit a block.
“does anything clash?”, “can one person attend all?” After sorting, only neighbours need checking.
“free time”, “gaps”, “uncovered” Gaps are the spaces between merged blocks.
IP ranges, memory blocks, version ranges, page ranges Same shape, different units. Watch for closed ends.
“how many at once?”, “peak load” Needs the event view: see sweep line.

How it works

Section titled “How it works”

The overlap test

Section titled “The overlap test”
  1. Take the later of the two starts, lo = max(a.start, b.start), and the earlier of the two ends, hi = min(a.end, b.end).
  2. They overlap if lo ≤ hi (closed) or lo < hi (half-open), and the shared part is [lo, hi].
overlap.py
Interval = tuple[int, int]




def overlaps_closed(a: Interval, b: Interval) -> bool:
    """Closed [s, e]: both ends belong, so [1, 3] and [3, 5] share the point 3."""
    return max(a[0], b[0]) <= min(a[1], b[1])  # 1. later start <= earlier end




def overlaps_half_open(a: Interval, b: Interval) -> bool:
    """Half-open [s, e): the end is excluded, so [1, 3) and [3, 5) only touch."""
    return max(a[0], b[0]) < min(a[1], b[1])  # 1. same test, strict




def intersection(a: Interval, b: Interval) -> Interval | None:
    """The shared part of two closed intervals, or None."""
    lo, hi = max(a[0], b[0]), min(a[1], b[1])  # 2. overlap, if any, is [lo, hi]
    return (lo, hi) if lo <= hi else None




if __name__ == "__main__":
    assert overlaps_closed((1, 3), (3, 5))
    assert not overlaps_half_open((1, 3), (3, 5))
    assert overlaps_closed((1, 10), (4, 6))      # containment counts
    assert not overlaps_closed((1, 2), (3, 4))   # neighbours on the integer line
    assert intersection((2, 7), (5, 12)) == (5, 7)
    assert intersection((1, 3), (3, 5)) == (3, 3)  # a single point
    assert intersection((1, 2), (4, 5)) is None
    print("ok")

Sort, then scan

Section titled “Sort, then scan”

The merge in the visualization above follows this template, and so do most interval problems:

  1. Sort by start (break ties by end if output order matters).
  2. Walk left to right, keeping one small summary: the current block’s end, or the latest end seen.
  3. For each interval, either it overlaps the summary (extend with max, or report a clash) or it doesn’t (close the block, start a new one).

Two small building blocks in that style: a conflict check (only adjacent pairs matter after sorting), and a point query that uses two sorted lists instead of a scan.

sorted scans.py
from bisect import bisect_left, bisect_right


Interval = tuple[int, int]




def has_conflict(meetings: list[Interval]) -> bool:
    """True if any two half-open [s, e) ranges overlap."""
    ordered = sorted(meetings)                      # 1. sort by start
    for prev, cur in zip(ordered, ordered[1:]):     # 2. only neighbours can be the first clash
        if cur[0] < prev[1]:
            return True
    return False




def count_covering(intervals: list[Interval], x: int) -> int:
    """How many closed [s, e] intervals contain x, using two sorted lists."""
    starts = sorted(s for s, _ in intervals)        # in a real system, build these once
    ends = sorted(e for _, e in intervals)
    started = bisect_right(starts, x)               # 3. intervals with s <= x ...
    finished = bisect_left(ends, x)                 #    ... minus those with e < x
    return started - finished




if __name__ == "__main__":
    assert has_conflict([(9, 10), (1, 4), (3, 5)])
    assert not has_conflict([(1, 3), (3, 5), (5, 6)])  # touching is fine
    assert not has_conflict([])
    ivs = [(1, 4), (2, 6), (5, 8), (9, 9)]
    assert count_covering(ivs, 5) == 2
    assert count_covering(ivs, 4) == 2   # closed: 4 is inside [1, 4]
    assert count_covering(ivs, 9) == 1
    assert count_covering(ivs, 0) == 0
    print("ok")

What it costs

Section titled “What it costs”
Operation Time Extra space
Overlap test of two intervals O(1) O(1)
Any operation that needs sorting first (merge, conflicts, gaps) O(n log n) sort + O(n) scan O(n) for the sorted copy / output
Input already sorted (e.g. insert into a sorted, merged list) O(n), or O(log n) to find the spot with binary search O(n) output
Two sorted lists against each other O(n + m) with two pointers O(n + m)
“How many contain x?” with pre-sorted starts and ends O(log n) per query O(n)

The sort dominates. If the interviewer says “the input is already sorted” or “it’s a stream in start order”, the sort disappears and so should your O(n log n).

Variations you’ll meet

Section titled “Variations you’ll meet”
  • Merge all overlapping intervals (the viz above).
  • Insert one interval into a sorted, already-merged list: three phases (before, overlapping, after), no re-sort.
  • Intersect two sorted lists: two pointers; advance whichever interval ends first.
  • Gaps / free time: merge, then read off the spaces between blocks.
  • Remove the fewest to make the rest non-overlapping: this is a greedy problem. Sort by end, not start.
  • Max simultaneous: count with events, see sweep line. Or a min-heap of end times if you also need to assign resources.
  • Dynamic sets of intervals (add/remove/query): a sorted map keyed by start, or an interval tree.

Pitfalls

Section titled “Pitfalls”
  • Closed vs half-open. Decide before writing any code. Time ranges are usually half-open [start, end); integer ranges like IP blocks or page numbers are often closed. One character (< vs ≤) flips the answer for touching intervals.
  • “Adjacent” integers. With closed integer ranges, [1, 2] and [3, 4] don’t overlap, but some problems want them merged because no integer lies between. That’s start ≤ end + 1. Ask.
  • Extending with e instead of max(end, e). A contained interval like [2, 3] inside [1, 10] would shrink the block.
  • Mutating the input when you sort in place. Sort a copy unless you’re told it’s fine.
  • JavaScript’s default sort is lexicographic. [[10, 12], [9, 10]].sort() compares as strings. Always pass a comparator.
  • Empty input and single intervals. Your loop should handle both without a special case, or with an explicit early return.

In the interview

Section titled “In the interview”
  • Ask: closed or half-open? Can start == end (a point)? Can the input be empty, unsorted, or contain duplicates? May I modify it?
  • State the invariant: “After sorting, cur is the merged block containing everything seen so far that could still overlap; nothing earlier can.”
  • Say the complexity with the reason: “O(n log n) for the sort, O(n) scan; if the input arrives sorted it’s O(n).”
  • Expect follow-ups: insert without re-sorting, intervals arriving as a stream, millions of intervals with point queries (sorted arrays + binary search, or an interval tree), and “now count the maximum overlap” (switch to events).

Check yourself

Section titled “Check yourself”
Check yourself
pick one
Half-open ranges: [9, 10), [10, 11), [10, 12). After merging, how many intervals remain?
Check yourself
pick one
Your merge sorts by start and, on overlap, sets cur.end = next.end. Which input breaks it?
Check yourself
pick one
Why is it enough to compare each interval only with the current merged block, not with every earlier interval?

Practice on your own

Section titled “Practice on your own”

Classic exercises (not gym questions):

  • Given a list of meetings, can one person attend all of them?
  • Find the minimum number of intervals to remove so the rest don’t overlap.
  • Minimum number of arrows to burst balloons, where each balloon is a horizontal range and an arrow at x bursts every range containing x.
  • Given a sorted, merged list and a range [a, b] to delete, return what’s left.
  • Total length of the union of a set of segments.

Go deeper

Section titled “Go deeper”
Section titled “Related”
Sweep lineTurn intervals into events to count overlap at every point.
Greedy algorithmsPicking the most non-overlapping intervals: sort by end.
Sorting and comparatorsTie-breaks and stable sorts decide interval order.
Timestamps and windowsHalf-open time ranges in real systems.