Intervals
An interval is a pair [start, end] marking a range on a line - time, indices, coordinates, whatever the problem is measuring. Throughout this page a pair of intervals is written a = [a0, a1] and b = [b0, b1], so a0 is a's start and a1 is its end - the subscripts are the indices you'd write in code, a[0] and a[1]. Almost every interval problem is one of a handful of questions asked about a pile of these pairs: do any two overlap, what's left after merging the overlapping ones, where does a new one fit in, how many can coexist without overlapping, or how many are "live" at the same point. This page covers the vocabulary and the techniques that answer those questions; the problems that follow are all a variation on one of them.
How two intervals can relate
Two intervals can only sit in a small, fixed number of arrangements - five shapes cover every case a problem is likely to distinguish. Each one except equals has a mirror image too, found by swapping which interval you call a. Every interval problem is really a question about which of these it treats as the same case. (The exhaustive catalogue, Allen's interval algebra, splits them further by giving each shared-edge case a name of its own.)
These collapse into a handful of questions the sections below answer: do the two share any ground at all (everything except disjoint), what single range covers both of them, what stretch they share, does one swallow the other (containment and equals), and when they don't touch, how wide is the gap.
Primitives
Every algorithm further down is built out of the same short list of one-line helpers. Each one is derived in its own section below; this is the whole set in one place, in the form the solutions on this site use them.
| Primitive | Answers | Returns |
|---|---|---|
| isDisjoint | do the two miss each other entirely | bool |
| doesIntersect / doesIntersectStrictly | do they share any ground - strict form says touching is not sharing | bool |
| getMerged | what single range covers both | interval |
| getIntersection | what range do they share | interval - reversed if they do not intersect |
| getGap | how wide is the empty space between them | number - negative if they overlap |
| isInGap / isInGapStrictly | does a third interval fit between two neighbours | bool |
| doesContain | does a swallow b whole | bool - directional |
The overlap test
It's easier to reason about when two intervals don't touch at all than when they do. a and b fail to overlap in exactly two ways: b starts strictly after a has finished, or a starts strictly after b has finished:
Turning that into an overlap test means negating it, and negating an or is exactly what De Morgan's law is for. The law says a negation may be pushed inside a bracket as long as the connective flips - and becomes or, or becomes and - and both halves get negated. It comes in two mirror-image forms:
It is usually taught over sets rather than booleans, where shading the regions makes the equality visible instead of merely algebraic. Here is the and form: the region left unshaded by not (A and B) is the lens where the two sets meet, and combining everything outside A with everything outside B leaves exactly that same lens uncovered.
Now apply the first form. doesIntersect is just the negation of isDisjoint, and isDisjoint is an or of two comparisons, so the law converts it in a single step:
That last line is the overlap test itself - the one nearly every interval solution calls:
The >= is a choice rather than a consequence. It treats intervals as closed - both endpoints included - so two intervals sharing only a boundary point count as overlapping. Scheduling problems usually want the opposite, since a meeting ending at 10:00 does not conflict with one starting at 10:00, and that test falls out of the identical derivation with isDisjoint's two comparisons relaxed to >=:
Either way both halves are needed. Two intervals can miss each other in exactly two ways - a entirely before b, or b entirely before a - and each half catches one of them; a fourth row covers the boundary case where the two tests part company:
The first three rows are every arrangement there is, which makes this a proof rather than an example: each half is false in exactly one of them, so only demanding both rules out both. Row four is where the choice bites - [1,5] and [5,10] share exactly the point 5, and nothing in the geometry decides whether that counts.
Closed is the right default most of the time: it merges [1,4] and [4,5] into [1,5], counts the integer points a range covers, and answers "do these two events conflict at all". Which one a problem wants is settled by its examples, not its prose - the wording rarely commits either way, an example with a shared endpoint always does - and keeping the two under distinct names is what stops you reaching for the wrong one on autopilot.
The habit worth keeping: when a condition is awkward to state directly, state its opposite and negate it.
Merging two intervals
Once two intervals are known to intersect, they collapse into the single range covering both: [1,4] and [3,6] merge to [1,6]. That range starts at whichever start comes first and ends at whichever end comes last:
The min/max pair is doing real work here - you cannot just return one interval's bounds, because neither interval is guaranteed to supply both. Which one supplies which depends on the arrangement, and there are exactly four:
All four combinations occur, and min/max read the correct endpoint in each - including the two containment rows, where the merge is just the larger interval handed back unchanged. Anything narrower would drop a point one of the intervals covers; anything wider would invent a point neither covers.
Intersecting two intervals
Where merging takes the range covering either interval, intersecting takes the range covered by both: [1,4] and [3,6] intersect on [3,4]. It starts at whichever start comes last and ends at whichever end comes first - the inner pair of bounds, where getMerged took the outer pair:
Same four arrangements as the merge proof, and the same catch in reverse - neither interval is guaranteed to supply both bounds:
All four combinations occur, and max/min read the correct endpoint in each - including the containment rows, where the intersection is the smaller interval handed back unchanged. This assumes the two actually intersect; when they don't, max(a0, b0) lands past min(a1, b1) and the range comes back reversed - which is exactly what the next section measures.
The gap between two intervals
When two intervals don't intersect, the empty space between them runs from whichever ends first to whichever starts second:
Those are getIntersection's two values subtracted the other way round, so one pair of numbers describes both quantities and only the sign tells them apart:
Every arrangement lands on one of those three signs, which is what makes it exhaustive. Positive is a real gap of that width, and the first two rows show the formula does not care which interval came first. Zero means they touch. Negative means they intersect, and its size is exactly the width getIntersection would hand back - the band is drawn solid there because it is shared ground, not empty space. Checking doesIntersect first is what tells you which of the two you are holding.
When you need the empty space itself rather than its width - filling holes, listing missing ranges - stop one step short of the subtraction and keep both endpoints:
Same two numbers as getIntersection, swapped: the intersection runs from the later start to the earlier end, the gap from the earlier end to the later start. Only valid once isDisjoint says there is one - otherwise it comes back reversed, which is getIntersection's answer wearing the wrong hat.
Does an interval fit inside a gap?
getGap measures the space between two intervals; the next question a sorted list makes you ask is whether a third interval fits in that space. This is the first primitive here that takes three intervals - the two neighbours, named for where they sit on the line, and a candidate a. Whether a is allowed to rest against a neighbour is the same per-problem decision as the overlap test, so it comes in the same two flavours:
Both say the same thing - a starts after left ends and finishes before right starts - and differ only on whether "after" includes the boundary itself. Four arrangements land the same way under either one, and a fifth is where they part company:
Rows two through four fail whichever test you reach for, and they are why neither half stands alone: each one satisfies the comparison on its own side while a still runs into the neighbour on the other. Row five is the whole difference between the two - a starts exactly where left ends, and only the operator decides.
With left = [1,2] and right = [8,9]: [4,6] sits clear and fits under both, [1,6] starts inside left and fits under neither, and [2,6] rests on left's end - which isInGap accepts and isInGapStrictly rejects.
Read the other way round, either gap test is just "disjoint from left and disjoint from right", with the ordering left < a < right baked in by which endpoint each comparison picks - which is why it only makes sense on a list already sorted by start. That framing also shows which gap test belongs with which overlap test, and the pairing crosses over:
| Convention | Two intervals touching means | Overlap test | Matching gap test |
|---|---|---|---|
| Closed - the page default | they overlap | doesIntersect (>=) | isInGapStrictly (>) |
| Half-open - scheduling | no conflict | doesIntersectStrictly (>) | isInGap (>=) |
The operators look swapped because the two tests are complements: if touching counts as an overlap, then fitting in the gap has to rule touching out. Pick the row, not the name.
Before the first interval and after the last there is no neighbour to compare against, so a candidate landing there fails a test it should pass. Passing an infinite sentinel in place of the missing neighbour keeps one code path: isInGapStrictly(last_interval, [float("inf"), float("inf")], a) asks "does a sit entirely past the end of the list", because a1 < inf is always true. A [-inf, -inf] sentinel does the same at the front, and both work unchanged for isInGap.
Containment
Merging and intersecting both hand back a range; containment just asks yes or no - does one interval swallow the other whole? [1,6] contains [3,4]. The <= on both sides means it still counts when the two share a start or an end, identical intervals included:
Unlike getMerged and getIntersection, this one is directional - doesContain(a, b) and doesContain(b, a) ask different questions. Both halves are needed again, and four rows cover every way the two comparisons can land:
Only the first row satisfies both. Rows two and three are why neither half is a test on its own - each one holds while b still escapes out the other end. Row four is row one with the arguments swapped, which is the directionality made visible: a no longer contains b, b contains a.
Containment always implies intersection - a swallowed interval overlaps its container by definition - but not the reverse, so reach for it only when a problem cares about full coverage (dropping intervals that add nothing to a merged result, say), not mere contact.
Sort first, always
An unsorted list of intervals tells you nothing without checking every pair against every other pair - O(n^2). Sorting turns that into a single left-to-right pass, but which key you sort by depends on what you're computing:
| Sort by | Unlocks | Used for |
|---|---|---|
| start | as you scan left to right, every interval you have not reached yet starts no earlier than the current one | merging overlapping intervals, inserting a new interval |
| end | the interval that frees up soonest is always a safe, optimal pick to keep | greedy scheduling: max non-overlapping, min removals to make the rest non-overlapping |
| start and end together, as +1/-1 events | a running count of how many intervals are open at any instant | counting overlaps at a point, minimum meeting rooms |
Building a new set of ranges
Merge overlapping intervals
Sort by start, then walk the list against the last interval kept: if the two intersect, replace that last one with the pair merged; otherwise it is finished, so append the current interval as the new last. The two primitives from above are the entire body of the loop.
Starting from an empty merged and guarding with if merged and ... avoids seeding the list with intervals[0] as a special case, and intervals.sort() sorts by start already - tuples and lists compare element by element, so the start is the primary key for free.
Sorting by start is what makes this a single pass: once an interval is confirmed done (the next start is past its end), nothing later in the sorted list can ever reach back and overlap it again.
A merge can create an overlap that didn't exist before - [1,3] merged with [2,8] becomes [1,8], which may now reach an interval neither one touched - so a brute-force pass has to restart after every merge: O(n^3) worst case, not O(n^2). Sorting doesn't speed up the same algorithm, it replaces "recheck everything after every change" with "adjacent is already in the right order."
Take [2,3], [4,5], [1,10]. By end the order is unchanged, and the loop emits [2,3], then merges [4,5] into [1,10] - which never looks back to absorb [2,3], though it fully contains it. Result [[2,3], [1,10]], wrong. By start it's [1,10], [2,3], [4,5] and both fold in on contact. Sorting by start guarantees nothing still ahead starts earlier than what you're merging into; sorting by end guarantees nothing.
Insert a new interval
A variant of merging: the list is already sorted and non-overlapping, and a single new interval needs to be dropped in - possibly merging with whatever it touches. Sorting the whole list again would work but throws away the fact that it was already sorted; a single linear scan in three phases does the same job without it.
The two while conditions are asymmetric on purpose: phase 1 stops as soon as an interval's end reaches new_interval's start (it might still overlap), while phase 2 keeps going as long as an interval's start is within new_interval's current end (which grows as more intervals are absorbed) - that growing boundary is exactly why new_interval[1] has to be re-checked with max() on every absorption, not just the first.
Selecting and counting intervals
Greedy interval scheduling
The question here isn't "what does the merged shape look like" but "how many of these can I keep without any two overlapping." Sort by end, not start: greedily keep an interval whenever its start is at or after the end of the last interval you kept.
Sorting by end is what makes the greedy choice safe: whichever interval ends soonest leaves the most room for everything after it, so it's never wrong to keep it over an interval that ends later. This is the same shape as "minimum removals to make the rest non-overlapping" - just len(intervals) - max_non_overlapping(intervals).
The simplest member of this family doesn't even need to count anything - "can one person attend every meeting" is just asking whether any two sorted intervals overlap at all:
Note that this whole scheduling family uses the strict comparison, not the closed-interval default from the top of the page: start >= last_end keeps a back-to-back interval, and start < prev_end only reports a conflict on a real overlap. That's deliberate - a meeting ending at 10:00 doesn't block one starting at 10:00. The merging and coverage sections above keep the >= form because there a shared endpoint means the two ranges genuinely join up.
Sweep line: counting overlaps at a point
Merging and greedy selection both answer "what does the set look like." A different family of questions - minimum meeting rooms, maximum overlapping intervals, busiest moment - asks something about a single instant instead.
Depth: the quantity being measured
Define the depth at a time t as how many intervals contain t:
Minimum meeting rooms is exactly max(depth(t) for all t), because at the busiest instant every one of those meetings is mid-flight and each needs its own room, and at no instant does anything need more. So the whole problem is: find the maximum of depth over the timeline. The timeline is continuous, so you cannot try every t.
Why only 2n points matter
depth is a step function. It can only change at a time where an interval starts or ends, because those are the only moments an interval enters or leaves the "contains t" set. Between two consecutive endpoints nothing changes, so the whole continuous timeline collapses to the 2n endpoints, and the maximum is guaranteed to be attained at one of them.
That is the sweep line: walk the endpoints left to right and maintain depth as you go, rather than recomputing it from scratch at each one.
Maintaining depth incrementally
Recomputing depth(t) at each of the 2n endpoints would be O(n²). But crossing an endpoint changes depth by exactly one, and you already know the direction: a start adds an interval, an end removes one. So tag each endpoint with its delta - +1 for a start, -1 for an end - sort the tagged endpoints by time, and depth becomes a running total that costs O(1) per event.
concurrent is the depth immediately after the current event, and peak is the running maximum, so the loop's invariant is exactly "the answer so far." Everything is O(n log n) for the sort plus O(n) for the sweep, and O(n) space for the event list.
(e[0], e[1]) and not just e[0]The tuple key sorts by time first and by delta second, and -1 < 1, so when a close and an open land on the same t the close is processed first. A meeting that ends at 10:00 frees its room in time for one starting at 10:00, so those two should count as one room, not two. Sorting on e[0] alone leaves the tie order up to which endpoint happened to be appended first, which makes the answer depend on input order.
This matches the strict < in the depth definition above: an interval [s, e] contains s but not e.
Step it yourself - the sweep line moves one event at a time, bars light up while they are open, and the depth chart draws itself only as far as the sweep has reached:
Two other shapes compute the exact same peak, and are worth recognizing since solutions online use all three interchangeably:
| Approach | What it tracks | When it reads clearer |
|---|---|---|
| Sweep line (events) | a running +1/-1 total over sorted event times | the answer is framed as "concurrency at a point", or you need every intermediate count, not just the peak |
| Min-heap of end times | the soonest-freeing room, popped whenever it is free before the next meeting starts | the answer is framed as "rooms" or "resources" - it's the most direct translation of the real-world allocation |
| Two sorted pointers (starts / ends) | a start-pointer and an end-pointer racing through two separately-sorted arrays | you only have the raw intervals and want to avoid building a heap or an explicit event list at all |
The heap version never grows past the number of rooms currently in use, so it's the tightest of the three on space; the two-pointer version needs no heap or event tuples at all, just two sorted arrays - both compute the same peak as the event sweep above.
Binary search on intervals
Every technique so far walks the whole list. Once the list is sorted, though, a single question asked about it - "which stored intervals does this new one touch?", "how many are live at this instant?" - should not cost a full pass. Binary search is what turns those into O(log n), and the surprise is that it needs no new idea: it is doesIntersect from the top of the page, read one more time.
You never binary search over pairs
bisect needs a sorted array of comparable scalars, and a list of [start, end] pairs is not that. So the first move is always the same - project the intervals onto two scalar arrays and search those:
starts is sorted because the list is sorted by start. ends is sorted only if the list is also disjoint, and that one condition splits this whole section in two.
Each half of the overlap test is one binary search
Take a list that is sorted and non-overlapping, and a query interval q. Ask the overlap test of every stored interval in turn:
Now look at each half as i runs left to right. ends ascends, so ends[i] >= q0 is false, false, false, then true and stays true. starts ascends, so starts[i] <= q1 is true, true, true, then false and stays false. Neither flips back. A predicate that flips exactly once over a sorted array is precisely what bisect locates the boundary of, so each half costs one binary search:
The and joining the two halves becomes an intersection of ranges, and since one is a suffix [lo, n) and the other a prefix [0, hi), the result is the half-open slice [lo, hi):
intervals[lo:hi] is exactly the set that intersects q, and everything below is a different question asked about that one slice. An empty slice (lo == hi) means nothing was touched.
The closed/strict choice crosses over again
bisect_left and bisect_right differ only on where they place a value equal to an existing element, which is the same decision > versus >= makes on a shared endpoint. So the convention table from isInGap has a binary-search column, and it crosses over the same way:
| Convention | Overlap test | lo = firstTouching | hi = afterLastTouching |
|---|---|---|---|
| Closed - merging, coverage | doesIntersect (>=) | bisect_left(ends, q0) | bisect_right(starts, q1) |
| Half-open - scheduling | doesIntersectStrictly (>) | bisect_right(ends, q0) | bisect_left(starts, q1) |
Under the closed row a stored interval ending exactly at q0 is pulled into the slice; under the half-open row it is left out, because a meeting ending at 10:00 does not conflict with one starting at 10:00. Pick the row, not the function name.
When the list overlaps: depth by two independent searches
Drop the disjoint requirement and ends stops being sorted, which kills both searches above. The repair is to give up the pairing entirely: sort starts and ends as two independent arrays, and count instead of locate.
This is the depth of the sweep-line section, with the sweep removed. The sweep maintains depth incrementally and therefore has to visit the events in order; this computes depth at any single t in O(log n) with no ordering requirement at all, so the queries may arrive shuffled and each is answered on its own.
"Started minus finished" survives the lost pairing because every interval falls into exactly one of three buckets at time t: not yet begun (counted by neither term), already over (counted by both, so it cancels), or live (counted by the first only). Which start belongs to which end never enters the arithmetic.
ends is sorted only when the list is disjointThe slice primitive reads ends as an ascending array, and that is a consequence of non-overlap, not of sorting. [[1,10],[2,3]] is sorted by start and its ends are [10, 3], so bisect_left on them returns nonsense with no error. Merge first, or fall back to the depth primitive. The single cheapest guard is to build ends at the same moment you establish disjointness, never from raw input.
Choosing between the two
Three questions, in order:
- Is the list disjoint? Use the slice.
intervals[lo:hi]is the touched set, andhi - loanswers most of the rest. - Not disjoint, but only a count at a point is needed? Use depth. Two independent arrays, two
bisectcalls. - Not disjoint, and you need to know which interval? Binary search can only narrow the candidates - a heap or a max-end segment tree picks the winner among them.
| Question | Primitive | Expression |
|---|---|---|
| Does a new interval conflict with any stored one? | slice | hi - lo == 0 |
| Where does a new interval merge in? | slice | intervals[:lo] + [merged] + intervals[hi:] |
| Is a query range fully covered? | slice + doesContain | hi - lo == 1 and doesContain(intervals[lo], q) |
| Which stored interval contains this point? | slice with q0 == q1 | lo if lo < hi else none |
| How many intervals are live at this instant? | depth | countStarted(t) - countFinished(t) |
The two primitives never do the judging themselves. They locate a candidate, and doesContain, getMerged, doesIntersect - the primitives from the top of the page - decide what it means. That composition is the pattern: bisect narrows, the interval primitives judge.
When intervals is the answer
Reach for one of the three techniques above when a problem talks about:
- Ranges that might overlap - "intervals", "ranges", explicit
[start, end]pairs. - Scheduling or booking - "meetings", "calendar", "can you attend all", "minimum rooms".
- A running "how many are active" - "maximum overlap", "busiest point", "free time".
And pick the technique by what's actually being asked: merge if the answer is a new set of ranges, insert if a sorted set already exists and one range is being added to it, greedy if the answer is a count of how many you can keep or remove, sweep line (or its heap/two-pointer equivalents) if the answer is about concurrency at a single instant.
Variants at a glance
| Variant | Sort by | Approach | Example problem |
|---|---|---|---|
| Merge overlapping | start | extend the last kept end whenever the current interval intersects it | Merge Intervals |
| Insert into a sorted set | already sorted | three phases: copy before, absorb overlapping, copy after | Insert Interval |
| Remove the fewest overlapping | end | greedy: keep the interval that frees up soonest | Non-overlapping Intervals |
| Count maximum concurrent | events (+1 start, -1 end) | sweep the sorted events, track the running total and its peak | Meeting Rooms II |
| Find the gaps | start | track the last end, compare it against the next start | Missing Ranges |
| Intersect two lists | both already sorted | two pointers: take getIntersection, advance whichever ends first | Interval List Intersections |
Common mistakes
Reading the input as sorted. Every technique above except insert-into-sorted assumes sorted input, and nothing in the problem statement guarantees it. intervals.sort() is the first line; if it isn't, the merge loop silently produces a wrong answer instead of crashing.
Sorting by the wrong key. Start and end are not interchangeable: merging by end can miss a contained interval (see the gotcha above), and greedy scheduling by start keeps a long early interval that blocks several short ones. Pick the key from the table above, not by habit.
Getting < and <= backwards. [1,5] and [5,8] touch at a point: doesIntersect calls that an overlap, doesIntersectStrictly doesn't. Meeting rooms treats it as free (you can start as one ends), a merge usually treats it as one range. Decide which the problem wants before writing the comparison, because both versions look equally correct on the page.
Losing the last interval. The seed-and-append shape - start with merged = [intervals[0]], append inside the else - only flushes an interval when a later one fails to overlap, so the final accumulator is still in hand when the loop ends and has to be appended after it. The if merged and ... form used above sidesteps this entirely by never holding an interval outside the list.
Mutating the caller's list. intervals.sort() sorts in place, so the caller's list comes back reordered, and getMerged writing into merged[-1] can write into an interval object the caller still holds. Harmless in a judge harness that calls you once; not harmless when the same input is reused across test calls. sorted(intervals) and building fresh tuples cost one allocation and remove the question.
Insert Interval and Interval List Intersections are the only common problems that hand you sorted input, and they say so explicitly in the statement. If you are inferring sortedness from the sample input rather than reading it in the constraints, sort.
Practice
- Problems - the merge, insert, and scheduling set.