These are my data structures and algorithms notes, cleaned up into nineteen posts, one pattern at a time. This one covers intervals: the overlap test, the merge sweep, and counting how many ranges are alive at once, all worked on one day of studio bookings.
Intervals are pairs of numbers that mean “from here to there”: meetings, bookings, IP ranges, video segments, loan periods. The problems look different on the surface, but nearly all of them reduce to three moves: decide whether two intervals overlap, sweep a sorted list while growing a block, and count how many intervals are alive at once. This part comes right after Heap / Priority Queue because the third move is a min-heap of end times, and it runs alongside Greedy, which picks up the question of which intervals to keep. There are no separate prerequisites here, so the single module below is “Intervals” itself, taught as the foundation.
How to use this post: the method. Checkpoints have no answers on the page: work them out, then open the linked chat to have your answer checked.
Intervals
Foundation
Picture a recording studio with one shared booking sheet. Each line is a slot like 9 to 13. The questions people ask about that sheet are always the same kind: does this new slot clash with anything, when is the studio free today, and at the busiest moment how many people were trying to use it.
The mental model: an interval is a segment on a number line, and a list of intervals is a set of segments dropped on that line in random order. Random order is the whole difficulty. Once the segments are sorted by where they start, you can walk the line left to right and every question above becomes a single pass with a tiny amount of state: one number (the furthest end you have seen) or one heap (the ends of everything still running).
What it solves: any question about coverage (what is busy, what is free), conflict (do two things clash) or load (how many things at once) over a collection of ranges, in O(n log n) instead of comparing every pair in O(n²).
Mechanics
One worked example runs through the whole module. The studio has seven bookings for a day that runs from 8 to 20 (hours):
bookings = [(15, 17), (9, 13), (10, 11), (12, 14), (16, 17), (17, 18), (12, 13)]
Sorted by start, and labelled so the diagram can refer to them:
| Label | A | B | C | D | E | F | G |
|---|---|---|---|---|---|---|---|
| Booking | (9, 13) | (10, 11) | (12, 13) | (12, 14) | (15, 17) | (16, 17) | (17, 18) |
Step 1: pick an endpoint convention before anything else. A booking (15, 17) followed by (17, 18) is not a clash: one person walks out at 17 and the next walks in. That is the half-open convention, [start, end), where the start instant is included and the end instant is not. Integer ranges like “addresses 1 to 3” are usually closed, [lo, hi], where both ends are included. Every comparison below has a strict version and a non-strict version, and the convention decides which one is correct. Most interval bugs are this decision made implicitly.
Step 2: the overlap test. Two half-open intervals a and b fail to overlap exactly when one finishes before the other starts: a.end <= b.start or b.end <= a.start. Negate that (De Morgan) and you get the test:
a.start < b.end and b.start < a.end
Check it on the example. A = (9, 13) and D = (12, 14): 9 < 14 and 12 < 13, so they overlap (on [12, 13)). E = (15, 17) and G = (17, 18): 15 < 18 but 17 < 17 is false, so they do not, which is the handover at 17 we wanted. For closed intervals both comparisons become <=, because [9, 13] and [13, 14] share the point 13.
Step 3: sorting turns two comparisons into one. If a comes before b in start order, then a.start <= b.start < b.end, so the first half of the test is already true. The only question left is b.start < a.end. That is why nearly every interval algorithm starts with a sort: after it, “does the next one overlap?” is one comparison against something to its left.
Step 4: the merge sweep, and why you compare against the running end. Walk the sorted bookings keeping cur_end, the furthest end seen so far in the current busy block. For each booking (start, end):
- If start > cur_end, nothing seen so far reaches start. Every earlier booking ends at or before cur_end (that is what cur_end means), and every later booking starts at or after start (that is what sorting guarantees). So [cur_end, start) is genuinely free, and a new block begins.
- Otherwise the booking touches or overlaps the current block, and the block now reaches max(cur_end, end).
The invariant: after processing the first i sorted bookings, their union is a list of finished blocks plus one open block whose right edge is cur_end. A finished block never changes again, because every later booking starts at or after the start that closed it.
The word that matters is max. Booking B = (10, 11) sits entirely inside A = (9, 13). If you overwrite cur_end with B’s end you would believe the block ends at 11, and then C = (12, 13) would look like it opens a new block after a free hour [11, 12) that never existed. The block’s edge is the furthest end seen, not the most recent one.
Here is the sweep on the example, starting cur_end at the day’s start, 8:
| Booking | cur_end before | start > cur_end? | Free gap found | cur_end after |
|---|---|---|---|---|
| A (9, 13) | 8 | 9 > 8, yes | (8, 9) | 13 |
| B (10, 11) | 13 | no | none | 13 |
| C (12, 13) | 13 | no | none | 13 |
| D (12, 14) | 13 | no | none | 14 |
| E (15, 17) | 14 | 15 > 14, yes | (14, 15) | 17 |
| F (16, 17) | 17 | no | none | 17 |
| G (17, 18) | 17 | 17 > 17, no | none | 18 |
After the loop cur_end = 18 < 20, so the tail (18, 20) is free as well. Free gaps: (8, 9), (14, 15), (18, 20). Busy blocks: [9, 14) and [15, 18). Note G: under half-open, 17 == 17 means “touching”, and touching bookings leave no free time between them, so the non-strict branch is correct here.
Step 5: counting concurrency. The merge sweep answers “busy or not”. The load question, “how many at once”, needs a count, and there are two standard ways to keep it.
Event sweep. Split every booking into two events: (start, +1) and (end, -1). Sort the events and add them up; the running total is the number of live bookings. The one decision is the tie at equal times. Under half-open, a booking that ends at 17 is gone at 17, so at the same time the -1 must be applied before the +1. Python’s tuple sort gives you this for free because -1 < +1 (recalled: tuples compare element by element). On the example the running total goes:
9: 1, 10: 2, 11: 1, 12: 2 then 3, 13: 2 then 1, 14: 0, 15: 1, 16: 2, 17: 1 then 0 then 1, 18: 0.
At 17, E and F end and G starts. Ends first gives 2, 1, 0, 1: the studio never holds more than one person at 17. Starts first would give 2, 3, 2, 1, and for an instant the count reads 3, reporting a three-way clash at 17 that did not happen.
Min-heap of end times. Process bookings in start order. Keep a min-heap holding the end times of bookings that have started. When a booking (start, end) arrives, pop every end <= start (those bookings finished at or before this one began), and the heap size is now exactly the number of bookings still running. Then push end.
Why only the top matters: the heap’s smallest end is the first booking to finish. If heap[0] > start, every other end in the heap is >= heap[0] > start, so all of them are still running and you can stop popping. Each end is pushed once and popped at most once, so the whole sweep costs O(n log n).
| Arriving booking | Popped (end <= start) | Live when it starts | Heap before pushing |
|---|---|---|---|
| A (9, 13) | none | 0 | [] |
| B (10, 11) | none | 1 | [13] |
| C (12, 13) | 11 | 1 | [13] |
| D (12, 14) | none | 2 | [13, 13] |
| E (15, 17) | 13, 13, 14 | 0 | [] |
| F (16, 17) | none | 1 | [17] |
| G (17, 18) | 17, 17 | 0 | [] |
The largest “live when it starts” is 2, at D, so with D included three bookings are running at 12, which matches the event sweep’s peak of 3 at 12. The two methods answer slightly different questions: the event sweep gives the count at every moment (a load profile), the heap gives the count at each arrival and keeps the identities of running bookings (their ends) available, which is what you need when the question is about the arriving interval itself.
Diagram
A timeline, one column per hour from 8 to 20. Each bar is a booking [start, end); B is drawn in amber because it hides inside A. The live row shows how many bookings cover each one-hour slot [h, h + 1). The green row marks the busy blocks, the dotted grey row the free gaps, and the dashed red line is the instant 17, where E and F end and G starts.
Three things to read off it. B hides inside A, which is why the merge sweep needs max. E and F both end exactly where G starts, which is where the tie rule lives. And the busy row is just “live >= 1” while the free row is “live == 0”, so the merge sweep and the count sweep are two views of the same line.
Implementation
The overlap test and the merge sweep, returning the free gaps in the day:
def overlaps(a, b):
# Half-open [start, end). a and b share an instant iff
# a[0] < b[1] and b[0] < a[1].
# Checked: (9, 13) vs (12, 14): 9 < 14 and 12 < 13 -> True.
# (15, 17) vs (17, 18): 17 < 17 is False -> False (handover at 17).
return a[0] < b[1] and b[0] < a[1]
def free_gaps(bookings, day_start, day_end):
"""Free (start, end) gaps inside [day_start, day_end) not covered by any booking.
Assumes every booking lies inside [day_start, day_end)."""
gaps = []
cur_end = day_start # right edge of the current busy block; day_start before any booking
# (recalled: sorted() returns a new list and orders tuples by start, then end;
# the input list is left untouched)
for start, end in sorted(bookings):
if start > cur_end:
# Every booking already processed ends at or before cur_end, and every
# booking still to come starts at or after start, so [cur_end, start)
# is free. Example: at E = (15, 17), cur_end = 14 -> gap (14, 15).
gaps.append((cur_end, start))
# Either start <= cur_end (touching or overlapping, e.g. G = (17, 18) with
# cur_end = 17) or a new block was just opened. In both cases the block now
# reaches max(cur_end, end). max, not end: B = (10, 11) inside A = (9, 13)
# must leave cur_end at 13, not 11.
cur_end = max(cur_end, end)
if cur_end < day_end:
# The loop only emits a gap when a later booking starts; the free time
# [cur_end, day_end) after the last block has no later booking to trigger it.
gaps.append((cur_end, day_end))
return gaps
bookings = [(15, 17), (9, 13), (10, 11), (12, 14), (16, 17), (17, 18), (12, 13)]
print(overlaps((9, 13), (12, 14))) # True
print(overlaps((15, 17), (17, 18))) # False
print(free_gaps(bookings, 8, 20)) # [(8, 9), (14, 15), (18, 20)]
The two concurrency sweeps, on the same bookings:
import heapq
def load_profile(bookings):
"""Step function [(time, live count from that time on)] for half-open bookings."""
events = []
for start, end in bookings:
events.append((start, +1))
events.append((end, -1))
# (recalled: tuples sort element by element, so at equal time (17, -1) comes
# before (17, +1)). Ends first is right for half-open: E and F leave at 17
# before G arrives at 17, so the count at 17 goes 2 -> 1 -> 0 -> 1, never 3.
events.sort()
profile, live = [], 0
for time, delta in events:
live += delta
if profile and profile[-1][0] == time:
profile[-1] = (time, live) # same instant: keep only the settled count
else:
profile.append((time, live))
return profile
def hours_at_least(profile, k):
"""Total time during which at least k bookings are live."""
total = 0
for (t, count), (t_next, _) in zip(profile, profile[1:]):
if count >= k:
total += t_next - t # count holds on [t, t_next)
return total
def live_at_arrival(bookings):
"""For each booking in start order: how many earlier bookings are still running when it starts."""
ends = [] # min-heap of end times (recalled: heapq is a min-heap, ends[0] is the smallest)
result = []
for start, end in sorted(bookings):
# Pop ends <= start: under half-open, a booking ending at 17 is gone at 17.
# Stop as soon as ends[0] > start: every other end is >= ends[0] > start,
# so every remaining booking is still running.
# Example: at G = (17, 18) the heap holds [17, 17]; both pop, live = 0.
while ends and ends[0] <= start:
heapq.heappop(ends)
result.append(((start, end), len(ends)))
heapq.heappush(ends, end)
return result
bookings = [(15, 17), (9, 13), (10, 11), (12, 14), (16, 17), (17, 18), (12, 13)]
profile = load_profile(bookings)
print(profile)
# [(9, 1), (10, 2), (11, 1), (12, 3), (13, 1), (14, 0), (15, 1), (16, 2), (17, 1), (18, 0)]
print(hours_at_least(profile, 2)) # 3 ([10, 11), [12, 13) and [16, 17))
print(live_at_arrival(bookings))
# [((9, 13), 0), ((10, 11), 1), ((12, 13), 1), ((12, 14), 2),
# ((15, 17), 0), ((16, 17), 1), ((17, 18), 0)]
Edge cases, run: free_gaps([], 8, 20) returns [(8, 20)]; free_gaps([(8, 20)], 8, 20) returns []; free_gaps([(9, 15), (10, 11), (12, 14)], 8, 20) returns [(8, 9), (15, 20)] (the containment case); load_profile([]) and live_at_arrival([]) return []; two identical bookings [(9, 11), (9, 11)] give the profile [(9, 2), (11, 0)] and live counts 0 then 1. I also checked every function against a brute-force “check every hour” version on 5,000 random booking sets.
Complexity, with n bookings: free_gaps, load_profile and live_at_arrival are O(n log n) time, dominated by the sort, plus (for live_at_arrival) n pushes and at most n pops on a heap of size at most n. Space is O(n) for the sorted copy, the 2n events or the heap. hours_at_least is O(n) over a profile of at most 2n points, and overlaps is O(1).
Recognition
Signals that an interval sweep applies:
- The input is a list of (start, end) pairs, or can be turned into one: meetings, bookings, ranges, segments, “from day x to day y”.
- The words overlap, conflict, clash, merge, cover, free time, at the same time, simultaneously, how many at once, minimum number of rooms, servers or resources.
- The order of the input is arbitrary and nothing in the problem depends on it, so sorting loses nothing.
- n is large enough (thousands and up) that comparing every pair in O(n²) is too slow.
Which list problems show which signal: Merge Intervals and Insert Interval are coverage questions (Insert Interval adds the signal “already sorted and non-overlapping”, which means you can skip the sort). Meeting Rooms is a pure conflict question. Meeting Rooms II is a “how many at once” question. Non Overlapping Intervals asks you to choose which intervals to keep, which is a selection question more than a sweep question. Minimum Interval to Include Each Query has the “set of live intervals” signal plus a second list, the queries, that you also get to process in whatever order you like.
When not to use it, and what it gets confused with:
- Tiny bounded coordinates (say all times are whole hours in 0 to 24, or days in a year): a difference array over the timeline, +1 at start and -1 at end followed by a prefix sum, is O(n + T) for T time slots and needs no sort. That is the event sweep without the sort, and it only works when T is small.
- Intervals arriving and disappearing online with queries in between: a single sort-and-sweep assumes you have everything up front. That needs a balanced tree or sorted container, not this.
- Sliding window is not this. A sliding window is a contiguous range of indices in one array that you choose; interval problems hand you ranges and ask how they relate to each other.
- Greedy selection is adjacent, not identical. The sweep tells you what overlaps; deciding which intervals to keep or drop needs its own argument about why the local choice is safe, and which endpoint you sort by is part of that argument. That is Part 13’s job.
Pitfalls
- Convention drift. Using <= in the overlap test for half-open intervals makes (15, 17) and (17, 18) clash. Using < for closed integer ranges makes [9, 13] and [13, 14] look disjoint even though both contain 13. Decide once, write it down, check the touching case.
- Overwriting instead of max. cur_end = end breaks on containment. On the example it invents a free gap (11, 12) because B = (10, 11) sits inside A = (9, 13).
- Forgetting to flush. The loop emits something only when a later interval triggers it. The last block, or the free tail (18, 20) here, has to be handled after the loop.
- Tie order in the event sweep. Ends before starts for half-open. For closed intervals it flips: [15, 17] and [17, 18] both contain 17, so the start at 17 must be counted before the end at 17, and you need an explicit sort key rather than relying on -1 < +1.
- Heap pop condition. while ends[0] < start instead of <= keeps E and F alive when G starts, so G reports 2 live bookings instead of 0.
- Sorting by the wrong key or not at all. sorted(bookings) sorts by start, then end. The merge sweep only needs start order; key=lambda b: b[0] works too. Sorting by end is a different algorithm with a different correctness argument, not a harmless variant.
- Mutating the caller’s list. list.sort() sorts in place; if the caller still needs their original order, use sorted().
- Zero-length intervals (start == end). Under half-open they contain no instant, but the two-comparison test still says (19, 19) overlaps (15, 20) because 19 < 20 and 15 < 19. In the event sweep a lone (12, 12) makes the running count dip to -1 for a moment because its -1 sorts before its +1. Either filter them out or decide what they mean.
- Empty input and single interval. Initialising cur_end to day_start (not to the first booking’s end) makes the empty case return the whole day as free without a special branch.
- Complexity claims. The sweep is O(n); the sort is O(n log n), so the whole thing is O(n log n). If the input is guaranteed sorted, say so and claim O(n).
Active Recall
Answer out loud or on paper first.
- In the merge sweep, when E = (15, 17) arrives with cur_end = 14, the code records (14, 15) as free without looking at A, B, C or D again. Why is that safe, and what would have to be true of the input for it not to be?
- Replace cur_end = max(cur_end, end) with cur_end = end and run the example. What does free_gaps return, and which booking causes the difference?
- At 17, E and F end and G starts. In the event sweep, what running counts do you see at 17 if ends are processed first, and what if starts are processed first? What does the heap version report for G if the pop condition is ends[0] < start?
- Suppose the studio switches to closed intervals, so a booking [9, 13] includes hour 13. Which comparisons in overlaps and free_gaps change, and do [9, 13] and [13, 14] overlap?
- In live_at_arrival, why is it enough to look only at ends[0], and why is the total cost O(n log n) even though one arrival can pop many ends (E pops three)?
Mini-task
The list problems here all announce themselves: they hand you pairs called intervals and ask about overlap, rooms or merging, so none of them makes you derive the sweep from scratch in disguise. This checkpoint stays in so the mechanics get exercised on something that does not look like a textbook interval problem.
A firewall keeps a blocklist of IPv4 address ranges, stored as integers and written as inclusive pairs [lo, hi]. Different teams add ranges independently, so ranges repeat, overlap and nest. Given the list, return how many distinct addresses are blocked. There can be up to 10^5 ranges, and the addresses span about 4.3 billion values, so you cannot mark them one by one.
Example: [[5, 9], [1, 3], [4, 4], [8, 12], [20, 22], [10, 11]] should return 15.
Before opening the chat, write down: the observation, the approach, why it’s correct, the complexity.
Transfer test
A video CDN logs each stream as (start_ms, end_ms, bitrate_mbps), with the stream released at end_ms. Capacity planning wants the peak total bandwidth ever in use at one instant. Would you use this module? Why, and which version?
Integration
How the pieces connect to the topic. Every interval problem in this list is some combination of three things from this module: the overlap test under a chosen convention, a sort that makes one comparison against the left side enough, and a sweep that keeps the minimum state to answer the question. Coverage questions keep one number (the running end). Load questions keep a counter over events or a min-heap of ends. Questions about the arriving interval itself (“what is still alive when this one starts”) keep a heap of the live intervals.
Distinguishing competing approaches:
| Approach | State kept | Answers | Cost |
|---|---|---|---|
| Pairwise overlap test | none | any question, slowly | O(n²) |
| Merge sweep (sort by start) | running end | coverage: blocks, gaps, total covered | O(n log n) |
| Event sweep | running count or sum | load at every instant, weighted load | O(n log n) |
| Min-heap of ends | ends of live intervals | load at each arrival, which intervals are live | O(n log n) |
| Difference array | array over time slots | load when coordinates are small integers | O(n + T) |
Two questions separate them fast. Is the question about coverage (busy or not) or about load (how many)? And is it asked about every instant, or about each interval as it arrives? A third question sits on the boundary with Greedy: are you asked to choose intervals, not just describe them? Then the sort order is part of a correctness argument you have to make, and the sweep is only the vehicle.
A recognition checklist for an unfamiliar problem:
- Can the input be read as ranges on a line? Times, positions, IDs, days, addresses all count.
- Is the endpoint convention half-open or closed? Write down what happens when one range ends exactly where another starts.
- Is order irrelevant, so sorting is free? If it is already sorted, can you skip the sort?
- Coverage, load, or choice? Coverage means a running end, load means a counter or heap, choice means a greedy argument.
- Every instant or each arrival? Every instant points to events, each arrival points to a heap.
- Is there a second list (queries, points, rooms) you can also sort and sweep against the first?
- Is the coordinate range tiny? Then a difference array might beat the sort.
- Does the complexity target allow O(n²)? If not, the sort-plus-sweep is almost certainly the intended shape.
The problems
Work these with the solving cycle from Part 1: a 15-minute honest struggle, one key sentence per problem, spaced repetition. For Intervals the struggle questions are: why does the local choice stay globally optimal? Is it a sort, a heap, or both? After watching a solution, justify the greedy decision in your own words: why this sort key, why this comparison, why this tie rule.
6 problems · 1 easy · 4 medium · 1 hard · tracker spreadsheet (.xlsx)
| # | Problem | Difficulty | Coach |
|---|---|---|---|
| 1 | Insert Interval | Medium | ChatGPT · Claude |
| 2 | Merge Intervals | Medium | ChatGPT · Claude |
| 3 | Non Overlapping Intervals | Medium | ChatGPT · Claude |
| 4 | Meeting Rooms | Easy | ChatGPT · Claude |
| 5 | Meeting Rooms II | Medium | ChatGPT · Claude |
| 6 | Minimum Interval to Include Each Query | Hard | ChatGPT · Claude |
Take this lesson as a live session
If you want this lesson interactively, with a coach that actually waits for your answers, open the full lesson prompt in a chat.