Interval basics & overlap
In one line
An interval is a [start, end] range, and two intervals overlap exactly when each one starts before the other ends: a.start <= b.end and b.start <= a.end.
What it is
An interval is a pair [start, end] describing a range of time, numbers or positions, such as a meeting from 9 to 10 or bytes 100 to 199 of a file. Interval problems ask whether ranges overlap, how to combine them, or how many are active at once.
The single most useful fact: two intervals a and b overlap if and only if a.start <= b.end and b.start <= a.end. It is easier to remember the opposite: they do not overlap when one ends before the other starts.
Be clear whether intervals are closed [start, end], where touching ends overlap, or half-open [start, end), where a meeting ending at 10 does not clash with one starting at 10. Calendars usually behave half-open, and the comparison changes from <= to <.
Why interviewers ask
Almost every interval question (merge, insert, meeting rooms, scheduling) is built on the overlap test and on sorting by start or end. Interviewers check that you write the condition correctly, ask about touching endpoints, and know the intersection formula without drawing every case.
How it works
- 1Represent each interval as [start, end] with start <= end.
- 2Overlap test (closed intervals): a.start <= b.end and b.start <= a.end. For half-open intervals use < in both places.
- 3If they overlap, the intersection is [max(a.start, b.start), min(a.end, b.end)]: start at the later start, end at the earlier end.
- 4The union of two overlapping intervals is [min of starts, max of ends].
- 5For lists of intervals, sort first: by start for merging and inserting, by end for choosing the most non-overlapping intervals.
- 6To intersect two sorted, non-overlapping lists, walk them with two pointers and always advance the interval that ends first, since it cannot overlap anything further on.
Worked example · Intersect A = [[0, 2], [5, 10]] with B = [[1, 5], [8, 12]]
- i = 0, j = 0: compare [0, 2] and [1, 5]. lo = max(0, 1) = 1, hi = min(2, 5) = 2. 1 <= 2, so add [1, 2]. A's interval ends first (2 < 5): i = 1.
- i = 1, j = 0: compare [5, 10] and [1, 5]. lo = 5, hi = 5. 5 <= 5, so add [5, 5] (they touch at one point). B's ends first: j = 1.
- i = 1, j = 1: compare [5, 10] and [8, 12]. lo = 8, hi = 10: add [8, 10]. A's ends first: i = 2, A is finished.
- Result: [[1, 2], [5, 5], [8, 10]] in O(m + n) time.
Picture it
Two people's lunch breaks overlap if each one starts their break before the other one comes back. If one person is already back before the other leaves, they never meet.
Reference code
def overlaps(a, b):
# closed intervals [start, end]: touching ends count as overlap
return a[0] <= b[1] and b[0] <= a[1]
def interval_intersection(A, B):
# A and B are each sorted and internally non-overlapping
i = j = 0
out = []
while i < len(A) and j < len(B):
lo = max(A[i][0], B[j][0]) # latest start
hi = min(A[i][1], B[j][1]) # earliest end
if lo <= hi:
out.append([lo, hi])
if A[i][1] < B[j][1]: # drop the one that ends first
i += 1
else:
j += 1
return out
print(interval_intersection([[0, 2], [5, 10]], [[1, 5], [8, 12]]))
# [[1, 2], [5, 5], [8, 10]]overlaps is the one-line test. interval_intersection walks two sorted lists; the interval that ends first is finished because every later interval in the other list starts even later. Each step advances one pointer, so it runs in O(m + n).
Key patterns
Overlap test
When: Any two intervals
How: a.start <= b.end and b.start <= a.end; switch to < for half-open intervals.
Intersection formula
When: You need the shared part
How: [max(starts), min(ends)], valid only if the max start <= min end.
Two-pointer list intersection
When: Two sorted lists of disjoint intervals
How: Compare current pair, record the intersection, advance whichever ends first. O(m + n).
Choose the sort key
When: Before working on a list
How: Sort by start to merge or insert; sort by end to pick the most non-overlapping intervals.
Real-world use
Calendar free/busy
Google Calendar and Outlook check a new event against existing events with an overlap test to warn about conflicts, and intersect people's free time to suggest meeting slots.
Database range types
PostgreSQL has range types like tstzrange with an && (overlaps) operator, and an exclusion constraint (EXCLUDE USING gist) can stop two bookings of the same room from overlapping at the database level.
HTTP range requests
Video players and download managers request byte ranges (Range: bytes=0-1023); servers and caches compare and combine these ranges to serve partial content.
Genomics
Tools like bedtools intersect gene coordinates with sequencing read positions to find which reads fall inside which genes, often across millions of intervals.
In a project
A clinic booking app must show a patient the times when both the chosen doctor and a free treatment room are available tomorrow.
- Load the doctor's free slots and the room's free slots as two lists of half-open intervals, each sorted by start.
- Intersect them with the two-pointer walk: compute the latest start and earliest end, keep it if it is non-empty, advance the slot that ends first.
- Drop intersections shorter than the appointment length (for example 30 minutes).
- Return the remaining slots to the app; recompute whenever a booking changes.
Impact: Patients only see times that truly work for both doctor and room, double bookings disappear, and the check runs in linear time even for a full day of 5-minute slots.
Trade-offs
Use it when
- The data is ranges of time, numbers or positions
- You need conflicts, shared time, coverage or counts of active ranges
- Lists can be sorted once and scanned
Avoid it when
- You must answer many overlap queries on a changing set: use an interval tree or a balanced tree, O(log n + k) per query
- Ranges are tiny integers in a small universe: a boolean array or a difference array may be simpler
Cost: One overlap test is O(1). Intersecting two sorted lists is O(m + n). Sorting an unsorted list first costs O(n log n).
Common mistakes
- Writing the overlap test with only one comparison, such as a.start < b.end, which misses the case where b ends before a starts.
- Not asking whether touching endpoints count as overlap (closed vs half-open).
- Listing six or more overlap cases by hand instead of using the two-comparison test or the negation.
- Advancing both pointers in list intersection, which skips overlaps.
- Assuming the input is sorted when the problem does not say so.
Interview questions
Quick revision
- Overlap (closed): a.start <= b.end and b.start <= a.end.
- No overlap: a.end < b.start or b.end < a.start.
- Half-open [s, e): use < instead of <=.
- Intersection: [max(starts), min(ends)] if valid.
- Union of overlapping pair: [min(starts), max(ends)].
- Two sorted lists: advance whichever ends first.
- Sort by start to merge; by end to schedule.
Check yourself
1. Do [1, 5] and [5, 8] overlap as closed intervals?
2. What is the intersection of [3, 9] and [6, 12]?
3. When intersecting two sorted interval lists, which pointer moves?
4. Which condition means intervals a and b do NOT overlap (closed)?
Saved on this device. Create a free account to keep it on every device.
Practise this with Sam
A real mock interview, out loud, with an honest scorecard. Free to start.