Merge Intervals, Insert Interval and Meeting Rooms
28 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)Interval problems ask about ranges such as meetings, bookings or ticket validity. Almost all of them become easy once the ranges are sorted by start. Then one sweep from left to right is enough.
Sort by start, then sweep to merge
An interval is a range with a start and an end, such as a booking from hour 2 to hour 6. Two intervals overlap when each one starts before the other one ends.
Bookings are given as start and end hours. Two bookings overlap when the next one starts before the current one ends. Sort by start, then extend the last merged range or begin a new one.
def merge(intervals): merged = [] for start, end in sorted(intervals): if merged and start <= merged[-1][1]: merged[-1][1] = max(merged[-1][1], end) else: merged.append([start, end]) return merged
print(merge([[1, 3], [2, 6], [8, 10], [9, 12], [15, 18]]))Example 1 · Brute force: join ranges until nothing changes
ranges = [[8, 10], [1, 3], [2, 6], [9, 12]]changed = Truewhile changed: changed = False for i in range(len(ranges)): for j in range(i + 1, len(ranges)): a, b = ranges[i], ranges[j] if a[0] <= b[1] and b[0] <= a[1]: ranges[i] = [min(a[0], b[0]), max(a[1], b[1])] del ranges[j] changed = True break if changed: breakprint(sorted(ranges))[[1, 6], [8, 12]]
What this code does
- It compares every pair again and again until no pair overlaps, so it costs up to O(n cubed) time.
- Sorting first removes all the repeated comparing.
Example 2 · Merge after sorting
ranges = [[8, 10], [1, 3], [2, 6], [9, 12]]merged = []for start, end in sorted(ranges): if merged and start <= merged[-1][1]: merged[-1][1] = max(merged[-1][1], end) else: merged.append([start, end])print(merged)[[1, 6], [8, 12]]
What this code does
- After sorting, only the last merged range can overlap the next one.
- The result is the same as the brute force, in O(n log n) time and O(n) space for the output.
Sorting costs O(n log n), and the sweep is O(n). The max matters, because a later interval can end before the merged one does.
Insert an interval into a sorted list
The list is already sorted and has no overlaps. A new interval arrives. Copy everything that ends before it, merge everything that touches it, then copy the rest. One pass is enough.
def insert(intervals, new): result, i = [], 0 while i < len(intervals) and intervals[i][1] < new[0]: result.append(intervals[i]) i += 1 while i < len(intervals) and intervals[i][0] <= new[1]: new = [min(new[0], intervals[i][0]), max(new[1], intervals[i][1])] i += 1 result.append(new) return result + intervals[i:]
print(insert([[1, 3], [6, 9]], [2, 5]))Example 3 · Insert [4, 8] into a sorted list
intervals = [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]]new = [4, 8]result, i = [], 0while i < len(intervals) and intervals[i][1] < new[0]: result.append(intervals[i]) i += 1while i < len(intervals) and intervals[i][0] <= new[1]: new = [min(new[0], intervals[i][0]), max(new[1], intervals[i][1])] i += 1result.append(new)result += intervals[i:]print(result)[[1, 2], [3, 10], [12, 16]]
What this code does
- [1, 2] ends before 4, so it is copied. [3, 5], [6, 7] and [8, 10] touch the new range, so they join it into [3, 10].
- [12, 16] is copied last.
It never sorts, so it costs O(n) time. The three phases are: before, overlapping and after.
Meeting rooms: one person, then many rooms
A sweep walks over sorted items from left to right once, keeping a small state such as the last end time, so that no pair of items has to be compared directly.
Can one person attend every meeting? Sort by start and check that each meeting starts at or after the previous one ends. How many rooms are needed at once? Track end times in a min-heap.
import heapq
def rooms_needed(meetings): ends = [] for start, end in sorted(meetings): if ends and ends[0] <= start: heapq.heapreplace(ends, end) else: heapq.heappush(ends, end) return len(ends)
print(rooms_needed([(0, 30), (5, 10), (15, 20)]))Example 4 · Can one person attend every meeting?
meetings = [(0, 30), (5, 10), (15, 20)]meetings.sort()ok = all(meetings[i][1] <= meetings[i + 1][0] for i in range(len(meetings) - 1))print(ok)False
What this code does
- After sorting by start, only neighbours can clash.
- (0, 30) is still running when (5, 10) starts, so the answer is False.
Example 5 · Minimum rooms with two sorted lists
meetings = [(0, 30), (5, 10), (15, 20)]starts = sorted(s for s, _ in meetings)ends = sorted(e for _, e in meetings)rooms = best = 0j = 0for start in starts: while ends[j] <= start: j += 1 rooms -= 1 rooms += 1 best = max(best, rooms)print(best)2
What this code does
- Each start adds a room in use, and each end that has already passed frees one.
- The biggest count seen is the answer. It costs O(n log n) for the sorts and O(1) extra space for the scan.
The heap holds one end time per room in use. A meeting reuses the room that frees up first, so the time is O(n log n).
Which edge cases decide an interval problem
Most wrong answers come from touching ranges, empty input and unsorted input. Settle each before you code.
- Touching ranges such as [1, 3] and [3, 5]: the problem statement decides if they merge.
- Unsorted input: sort first, unless the statement promises sorted order.
- One range inside another: use
maxon the end, never just copy it. - Empty input: return an empty result before you read
intervals[0].
Next step
Check your understanding
10 quick questions