Merge Intervals in Python: Overlaps, Rooms and Scheduling
Problems About Time Slots and Ranges
A lecture timetable, a list of hall bookings, the hours a generator ran, the ranges of pages a student has read: all of these are lists of intervals, each with a start and an end. Questions about them come up constantly in real software and in programming interviews. Which bookings overlap? What are the combined busy periods? How many halls are needed so that no two lectures clash? This tutorial covers the core merge intervals technique, inserting a new interval, finding overlaps between two schedules, counting the rooms needed with a sweep line, and removing the fewest intervals to eliminate overlaps, all in Python with outputs checked by running the code. The common thread is simple: sort first, then scan once.
Representing Intervals
We represent each interval as a pair [start, end]. For times, using minutes or hours as numbers keeps the code simple: 9:30 can be 9.5 or 570 (minutes since midnight). Before writing code, decide whether touching intervals overlap: does a booking ending at 10:00 clash with one starting at 10:00? Here we treat [1, 3] and [3, 5] as touching and merge them when merging busy periods, but as not clashing when booking rooms. Always check which rule a problem wants.
Two intervals [a, b] and [c, d] overlap (share some time) exactly when a < d and c < b. Both conditions say "each one starts before the other ends".
Merge Intervals: Combining Overlapping Ranges
Given a list of intervals in any order, combine all overlapping ones. The method:
- Sort the intervals by start time.
- Go through them in order. If the next interval starts at or before the end of the last merged interval, extend that merged interval's end. Otherwise, begin a new merged interval.
def merge(intervals):
result = []
for start, end in sorted(intervals):
if result and start <= result[-1][1]:
result[-1][1] = max(result[-1][1], end) # overlap: extend
else:
result.append([start, end]) # gap: new interval
return result
print(merge([[1, 3], [8, 10], [2, 6], [15, 18]]))
print(merge([[1, 4], [4, 5]]))
print(merge([[1, 10], [2, 3], [4, 5]]))
Output:
[[1, 6], [8, 10], [15, 18]] [[1, 5]] [[1, 10]]
The max in the extend step matters: when one interval sits completely inside another, like [2, 3] inside [1, 10], the end must not shrink. Sorting costs O(n log n) and the scan is O(n), so merging takes O(n log n) overall.
Example: Total Hours the Generator Ran
Merging is the first step for many "total time" questions. If several people logged the times they switched a generator on (with overlapping entries), the true running time is the total length of the merged intervals:
logs = [(18, 21), (19, 23), (6, 8), (7, 9), (22, 24)] # hours of the day merged = merge(logs) print(merged, sum(e - s for s, e in merged), "hours")
Output:
[[6, 9], [18, 24]] 9 hours
Inserting a New Interval
If the list is already sorted and non-overlapping, a new interval can be inserted in a single O(n) pass without re-sorting: copy the intervals that end before it, merge everything that overlaps it, then copy the rest.
def insert(intervals, new):
result, i, n = [], 0, len(intervals)
s, e = new
while i < n and intervals[i][1] < s: # entirely before
result.append(intervals[i]); i += 1
while i < n and intervals[i][0] <= e: # overlapping: absorb
s = min(s, intervals[i][0]); e = max(e, intervals[i][1]); i += 1
result.append([s, e])
result.extend(intervals[i:]) # entirely after
return result
print(insert([[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], [4, 8]))
Output:
[[1, 2], [3, 10], [12, 16]]
Free Slots Common to Two Schedules
To find when two students are both busy, walk through both sorted lists with two pointers. The overlap of [a, b] and [c, d] is [max(a, c), min(b, d)], if that is a valid interval. Then advance whichever interval ends first.
def intersections(A, B):
i = j = 0
out = []
while i < len(A) and j < len(B):
lo = max(A[i][0], B[j][0])
hi = min(A[i][1], B[j][1])
if lo < hi:
out.append([lo, hi])
if A[i][1] < B[j][1]:
i += 1
else:
j += 1
return out
ada = [[8, 10], [12, 14], [16, 18]]
musa = [[9, 13], [15, 17]]
print(intersections(ada, musa))
Output:
[[9, 10], [12, 13], [16, 17]]
Combining this with merging gives free time: merge everyone's busy intervals, and the gaps between consecutive merged intervals are the free slots when a group meeting could be held.
How Many Lecture Halls? The Sweep Line
Given lecture times, what is the smallest number of halls so that no two lectures in the same hall overlap? The answer is the largest number of lectures happening at the same moment. A sweep line finds it: turn each lecture into two events, +1 at its start and −1 at its end, sort the events by time, and keep a running total.
def halls_needed(lectures):
events = []
for s, e in lectures:
events.append((s, 1))
events.append((e, -1))
events.sort() # at equal times, -1 sorts before +1: a hall frees up first
running = best = 0
for _, change in events:
running += change
best = max(best, running)
return best
timetable = [(8, 10), (9, 11), (10, 12), (11, 13), (9, 10)]
print(halls_needed(timetable))
print(halls_needed([(8, 9), (9, 10), (10, 11)]))
Output:
3 1
Sorting the tuples puts (10, −1) before (10, 1), so a lecture ending at 10 frees its hall for one starting at 10; back-to-back lectures can share a hall. Between 9 and 10, three lectures run at once, so 3 halls are needed. A heap of end times gives the same answer and also tells you which hall each lecture uses.
Removing the Fewest Intervals
Another classic: remove the minimum number of bookings so that the rest don't overlap. Equivalently, keep as many as possible. The greedy rule that works is: sort by end time, and repeatedly keep the booking that finishes earliest among those that don't clash with the last one kept. Finishing early leaves the most room for the rest.
def max_non_overlapping(intervals):
kept, last_end = [], float("-inf")
for s, e in sorted(intervals, key=lambda iv: iv[1]):
if s >= last_end:
kept.append((s, e))
last_end = e
return kept
bookings = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
kept = max_non_overlapping(bookings)
print(kept, "remove", len(bookings) - len(kept))
Output:
[(1, 4), (5, 7), (8, 11), (12, 16)] remove 7
Sorting by start time instead would fail: the booking (0, 6) starts first but blocks three others. This is the "activity selection" problem, a standard example of when a greedy algorithm is provably optimal.
Summary
- Intervals [a, b] and [c, d] overlap when a < d and c < b; decide whether touching counts.
- Merge intervals: sort by start, then extend the last merged interval or start a new one, in O(n log n).
- Insert into a sorted list in O(n); intersect two sorted lists with two pointers.
- The sweep line (+1 at starts, −1 at ends) gives the maximum overlap, which is the number of rooms needed.
- To keep the most non-overlapping intervals, sort by end time and choose greedily.