--- title: "Merge intervals: sort by start, one pass, and the four problems around it" url: https://algopath.pro/blog/merge-intervals language: en summary: "Sort by start, then extend the last interval or open a new one. Trigger words, Python code for Merge and Insert Interval, Meeting Rooms II, Non-overlapping Intervals and the mistakes." updated: 2026-10-29 --- # Merge intervals: sort by start, one pass, and the four problems around it **Short answer.** To merge intervals, sort them by start, then walk once. Each interval either extends the last one in the result or starts a new one. Time O(n log n) from the sort. The pattern covers meetings, busy slots, inserting a range and coverage. Below: trigger words, Python code, a traced run and the mistakes. ## What does it mean to merge intervals? An interval is a pair: start and end. Two intervals overlap when the second starts before the first ends. Merging replaces an overlapping pair with one interval. It runs from the smaller start to the larger end. Without sorting you would compare every pair. That is O(n²). After sorting by start, only the last merged interval can overlap the current. That is the whole pattern: sort, then one pass. ## When does a problem need you to merge intervals? - "Merge all overlapping intervals." - "Insert a new interval into a non-overlapping list." - "How many meeting rooms are needed." - "Can one person attend all meetings." The shared signal: start-end pairs and a question about overlap or coverage. If the question is "how many at the same time", that is the neighbouring sweep line pattern. ## How does the merge work step by step? - Sort the intervals by start. - Put the first one into the result. - For each next interval, look at the last one in the result. Its start is at most that end: they overlap. Set the end to the larger of the two ends. - Otherwise append the current interval as a new one. The max of the ends matters. The current interval may sit entirely inside the previous one. ## What does one run look like? Intervals [1, 3], [8, 10], [2, 6], [15, 18]. Sorted: [1, 3], [2, 6], [8, 10], [15, 18]. Result: [1, 3]. Take [2, 6]: 2 is at most 3, merge, result [1, 6]. Take [8, 10]: 8 is above 6, new interval. Take [15, 18]: new again. Final [1, 6], [8, 10], [15, 18]. ## How do you merge intervals in Python? ``` def merge(intervals): intervals.sort(key=lambda x: x[0]) result = [] for start, end in intervals: if result and start <= result[-1][1]: result[-1][1] = max(result[-1][1], end) # overlap else: result.append([start, end]) return result def insert(intervals, new): result, i, n = [], 0, len(intervals) while i < n and intervals[i][1] < new[0]: # entirely left result.append(intervals[i]); i += 1 while i < n and intervals[i][0] <= new[1]: # overlaps new new = [min(new[0], intervals[i][0]), max(new[1], intervals[i][1])] i += 1 result.append(new) result.extend(intervals[i:]) # entirely right return result ``` The second function inserts into an already sorted list without sorting. Three loops: before, overlap, after. Time O(n). ## How do the interval problems differ? | Problem | Sort by | Work in the pass | Time | | --- | --- | --- | --- | | Merge Intervals | Start | Extend the last result | O(n log n) | | Insert Interval | Already sorted | Three loops: before, inside, after | O(n) | | Meeting Rooms | Start | Find a start before the previous end | O(n log n) | | Meeting Rooms II | Start, plus a heap of ends | Track the peak of concurrent meetings | O(n log n) | | Non-overlapping Intervals | End | Greedily keep the earliest end | O(n log n) | ## How do you solve Meeting Rooms II? A list of meetings. Return the minimum number of rooms. Sort by start. Keep a min-heap of end times of running meetings. For each meeting, look at the earliest end in the heap. It is at most the new start: that meeting is over, pop it. Push the current end. The largest heap size is the answer. ## How do you solve Non-overlapping Intervals? Remove the fewest intervals so the rest do not overlap. Sort by end. Track the end of the last kept interval. An interval that starts before that end gets removed. Otherwise keep it and update the end. Sorting by end is the usual way. Sorting by start also works if, on an overlap, you keep the interval that ends first. ## What mistakes break a merge intervals solution? - Skipping the sort and merging only input neighbours. - Taking the current end instead of the max of ends. A nested interval shortens the result. - Mixing up strict and non-strict comparison on touching ends. [1, 3] and [3, 5] can be one interval or two. The statement decides. - Mutating tuples instead of lists and hitting an assignment error. ## How do you explain merge intervals in an interview? Say: I sort by start. Then only the last merged interval can overlap the current one. Give O(n log n) and note that the sort dominates. The pass is linear. Ask whether touching intervals count as overlapping. It shows you care about edges. Drill this pattern on the [intervals: merge and insert](/patterns/intervals-merge) page. The neighbouring pattern lives on the [sweep line](/patterns/sweep-line) page. ## FAQ ### Can you skip the sort? Only when the input is already sorted. Or when the coordinates are small integers. In the second case a difference array works in O(n + max). ### How do you intersect two interval lists? Two pointers, one per list. The intersection runs from the larger start to the smaller end. It exists when the start is at most the end. Advance the pointer whose interval ends first. ### What about open and closed ends? Decide once at the start and keep one comparison. Closed ends overlap when start is at most end. Open ends need strict less-than. ### Where does this pattern show up in real systems? Calendars looking for a free slot. Schedulers that merge busy windows. Disk allocators that join adjacent free blocks.