Working with intervals: half-open ranges, overlaps, merging and gaps
Bookings, shifts, diff hunks and time slots are intervals. Use half-open ranges, test overlap with one comparison, check clashes in O(log n), merge overlapping intervals and find free gaps.
Meeting rooms, parking stays, shifts, IP ranges and changed lines in a file are all intervals: a start and an end. A few rules handle nearly every interval problem.
Half-open intervals
Represent an interval as [start, end): start is included, end isn't.
[9:00, 10:00) and [10:00, 11:00) -> touch, don't overlap
length = end - start -> no +1
empty = start == endCheck start < end (or <=, if empty intervals are allowed) when an interval is created, so the
rest of the code never sees a backwards one.
Do two intervals overlap?
One line, no special cases:
overlaps(a, b) = a.start < b.end and b.start < a.endPeople often write four cases ("a starts inside b", "b starts inside a", "a contains b"…) and miss one. The one-liner covers them all. Test it with: touching on both sides, identical, one inside the other, and far apart.
Checking against many bookings
Comparing a new booking against every existing one is O(n). If bookings in a room never overlap
and are kept sorted by start (a std::map<start, end> in C++), only two neighbours can clash:
next = first booking with start >= new.start (lower_bound)
prev = the booking before next, if any
clash if (next exists and next.start < new.end) or (prev exists and new.start < prev.end)That's O(log n) per booking. See lower_bound and room bookings for Meetly.
Merging intervals
To combine overlapping intervals (for example, busy times from several calendars):
sort by start
result = [first]
for each interval x after the first:
if x.start <= result.last.end: result.last.end = max(result.last.end, x.end) # overlap or touch
else: result.append(x)Use <= to merge touching intervals too (busy 9–10 and 10–11 is busy 9–11), < to keep them
separate. The ticket decides which; the max is what people forget, when one interval lies
entirely inside the previous one.
Gaps: finding free time
Free time is the space between merged busy intervals, inside the window you're asked about:
cursor = window.start
for each busy interval b (merged, sorted), clipped to the window:
if b.start > cursor: free.append([cursor, b.start))
cursor = max(cursor, b.end)
if cursor < window.end: free.append([cursor, window.end))For "when are all of these people free?", merge everyone's busy times into one list first, then find the gaps. To keep only gaps long enough for a meeting, filter by length at the end.
Intervals in other places
- Stays across midnight: convert to minutes from a fixed point first, then it's an ordinary interval. See crossing midnight.
- Diff hunks: changed line ranges plus context lines on each side; hunks whose context ranges overlap or touch are merged into one, exactly like the merge above.
Questions and answers
- Why use half-open intervals [start, end)?
- Back-to-back ranges then share an endpoint without overlapping (9:00–10:00 and 10:00–11:00), the length is simply end − start, and an empty range is start == end. Closed ranges need +1 and −1 corrections everywhere.
- How do I check whether two intervals overlap?
- For half-open intervals, a and b overlap exactly when a.start < b.end and b.start < a.end. If either comparison fails, one ends before (or exactly when) the other starts.
Practise it in a project
These projects put this guide to work, with tickets, tests and code review.
Meetly
Room bookings for Meetly
Stop double bookings in Meetly's rooms with an ordered index, then find times when everyone is free by merging calendars.
- half-open intervals
- ordered maps
- interval merging
- lower_bound
ParkPoint
Parking fees for ParkPoint
Compute what ParkPoint's pay machines charge: stays across midnight, a free grace period, a daily cap and an evening flat rate.
- time arithmetic
- integer rounding
- business rules
- boundary testing
Mergebay
A diff engine for Mergebay
Compute minimal line diffs with the longest common subsequence, then render them as unified-diff hunks with context, exactly like the tools reviewers already know.
- dynamic programming
- LCS
- unified diff format
- edge cases