Merge Intervals (LC 56)(opens leetcode.com)
You're given an array of intervals, each entry [start_i, end_i]. Fuse together every pair of intervals that overlap, then return the resulting array of non-overlapping intervals that together cover the exact same span as the original input.
Merge Intervals
intervals ➔ sort by start time ➔ merge or extend prev.end| 1 | def merge_intervals(intervals: list[list[int]]) -> list[list[int]]: |
| 2 | """Interval Merging via chronological start-time sorting. |
| 3 | Time: O(N log N) | Space: O(N) |
| 4 | """ |
| 5 | if not intervals: |
| 6 | return [] |
| 7 | |
| 8 | # 1. Sort by Start Time: |
| 9 | # Sorting puts every interval that can overlap the current one directly after it, so one |
| 10 | # left-to-right pass is enough: no interval later in the list can start earlier than this one. |
| 11 | intervals.sort(key=lambda iv: iv[0]) |
| 12 | merged: list[list[int]] = [] # merged holds finished, disjoint intervals, in order |
| 13 | accumulated = intervals[0] # accumulated is the one interval still open for absorbing overlaps |
| 14 | |
| 15 | for incoming in intervals[1:]: |
| 16 | # 2. Absorb or Close the Accumulator: |
| 17 | # incoming overlaps accumulated exactly when incoming starts at or before accumulated's end; |
| 18 | # touching at one shared point still counts as overlap. |
| 19 | if incoming[0] <= accumulated[1]: |
| 20 | accumulated[1] = max(accumulated[1], incoming[1]) # Keep the later end: a nested interval must not shrink it |
| 21 | else: |
| 22 | merged.append(accumulated) # No later interval starts before accumulated ends, so it is finished |
| 23 | accumulated = incoming # Start a new accumulator from incoming |
| 24 | |
| 25 | # 3. Flush the Last Accumulator: |
| 26 | # The loop only saves accumulated when a later interval closes it, so the final open interval is saved here. |
| 27 | merged.append(accumulated) |
| 28 | return merged |
merged holds finished, disjoint intervals in order, and accumulated is the union of every interval seen since the last one was saved.Sort by start, then keep one accumulated interval open: if incoming[0] <= accumulated[1] the two overlap, so stretch accumulated[1]; otherwise save accumulated into merged and start again from incoming. After sorting, every later interval starts at or after incoming, so once one starts past the current end, nothing later can reach back into accumulated: it is finished. The trap is the end update: use max(accumulated[1], incoming[1]), because an interval nested inside another would otherwise shrink the merged end.
See it run
Merge Intervals, step by step
accumulated [1, 5]merged none
Each column is one time point. Each row of numbers is one interval, sorted by start. A dash marks the time points the interval covers. An equals sign marks the time points covered by a saved interval in merged.
startthe start time of incomingendthe end time of incomingaccthe start time or the end time of accumulatedsavedthe start time or the end time of an interval that was just appended to merged
Sort by start. accumulated = [1, 5], the first interval.
Gotcha 1 of 4
- The trap
Gotcha 1: Setting the end to
incoming[1]withoutmaxMistakeaccumulated[1] = incoming[1]Fixaccumulated[1] = max(accumulated[1], incoming[1])What happens:
incomingcan lie completely insideaccumulated. Thenincoming[1]is smaller thanaccumulated[1]. The plain assignment moves the merged end back toincoming[1]. A later interval that overlaps the old end is then saved as a separate interval.Example: intervals = [[1, 5], [2, 3], [4, 6]]Mistake: returns [[1, 3], [4, 6]]Fix: returns [[1, 6]]
- You must keep as many intervals as possible without overlap, or remove the fewest, as in Non-overlapping Intervals (LC 435): overlapping intervals are dropped, not combined. See Interval Scheduling
- The question is how many intervals overlap at the busiest moment, as in Meeting Rooms II (LC 253), not what their union looks like. See Sweep Line
Deep Dive
Why sorting by start makes one pass enough
Two intervals overlap when each one starts at or before the other one ends. Checking every pair would take O(N^2) time. Sorting by start removes the need for that.
After the sort, the intervals come in order of start time. incoming is the next interval, and every interval after it starts at or after incoming[0]. Suppose incoming[0] > accumulated[1]. Then every later interval also starts after accumulated[1], so none of them can reach back into accumulated. It is finished, and merged.append(accumulated) is safe.
If incoming[0] <= accumulated[1], the two intervals share at least one time point. Their union is one interval, so the loop stretches accumulated[1] and keeps going.
Example: in Merge Intervals (LC 56), intervals = [[1, 3], [2, 6], [8, 10], [15, 18]] is already sorted. accumulated starts as [1, 3]. [2, 6] starts at 2, which is at most 3, so accumulated becomes [1, 6]. [8, 10] starts at 8, which is greater than 6, so [1, 6] is saved. [15, 18] starts after 10, so [8, 10] is saved. The last flush saves [15, 18]. The answer is [[1, 6], [8, 10], [15, 18]].
One trace: the end only moves right
The board replays intervals = [[1, 5], [2, 3], [4, 6], [8, 9]]. Each column is a time point. The last two rows show accumulated and merged.
[2, 3] lies inside [1, 5]. The update is max(5, 3) = 5, so the end stays 5. This is the step marked as the trap on the board. Then [4, 6] starts at 4, which is at most 5, so the end moves to 6. [8, 9] starts at 8, which is greater than 6, so [1, 6] is saved.
If the update were accumulated[1] = incoming[1], the nested [2, 3] would move the end back to 3. Then [4, 6] would start at 4, which is greater than 3, and [1, 3] would be saved as a separate interval. The wrong answer is [[1, 3], [4, 6], [8, 9]]. The right answer is [[1, 6], [8, 9]].
After the sort, max is needed only because an incoming interval can end before accumulated does. Without a nested interval, the new end is always the larger one.
The final flush and the touching case
The loop saves accumulated only when a later interval closes it. The last interval has no later interval, so nothing closes it. The line merged.append(accumulated) after the loop saves it.
Example: for [[1, 3], [2, 6], [8, 10], [15, 18]], a version without the flush returns [[1, 6], [8, 10]]. The interval [15, 18] is lost. On the board above, the flush is the step before the last step.
The test is incoming[0] <= accumulated[1], not <. In Merge Intervals (LC 56), two intervals that share one end point are merged. For [[1, 4], [4, 5]], the start 4 equals the end 4, so the answer is [[1, 5]]. With <, the two intervals stay separate.
The blueprint also changes the caller's list. accumulated = intervals[0] points to the caller's own interval, and intervals.sort reorders the caller's list. Pass a copy when the input is needed again.
The cost, and which problems fit
The sort takes O(N log N) time. The loop is one pass with O(1) work per interval, so it takes O(N) time. The total is O(N log N). merged holds up to N intervals, so the extra space is O(N).
Example: 1000 intervals take about 10000 comparisons in the sort and 999 in the loop. The sort is the cost that grows fastest.
If the input is already sorted by start, skip the sort. Insert Interval (LC 57) gives a sorted list of disjoint intervals and one new interval, so it can be solved in O(N) time with the same absorb-or-close test.
Meeting Rooms (LC 252) asks whether any two intervals overlap. Sort by start, then check each incoming[0] against the previous end. Employee Free Time (LC 759) merges the intervals of all employees, and the gaps between the merged intervals are the answer.
If the question is how many intervals are open at the same time, merging loses that count. Use the Sweep Line card for it. If the question is how many intervals to keep or remove, use the Interval Scheduling card.
60-Second Pitch
"I sort the intervals by start time. Then I keep one open interval, accumulated, and a list of finished intervals, merged. For each incoming, I compare its start with the end of accumulated. If the start is at most that end, the two overlap, so I set the end to the larger of the two ends. Otherwise accumulated is finished, because every later interval starts even later. I save it and start a new one. After the loop I save the last accumulated. The sort costs O(N log N), the pass costs O(N), and merged uses O(N) space. The cases I check are a nested interval, two intervals that touch at one point, and a single interval."
Common Questions
- Why do you sort by start time and not by end time?
Sorting by start guarantees that every later interval starts at or after
incoming[0]. Whenincomingstarts pastaccumulated[1], no later interval can reach back, soaccumulatedcan be saved. Sorted by end, a later interval could start very early and overlap an interval that was already saved.- Why is
max(accumulated[1], incoming[1])needed? incomingcan lie completely insideaccumulated. Thenincoming[1]is smaller thanaccumulated[1], and a plain assignment would move the merged end back. For[[1, 5], [2, 3], [4, 6]], that mistake saves[1, 3]instead of continuing to[1, 6].- What are the time and space complexity?
O(N log N)time, because the sort dominates and the pass isO(N). The space isO(N)formerged, plus the space the sort uses. If the input is already sorted by start, the time isO(N).- Do two intervals that only touch at one point merge?
In Merge Intervals (LC 56), yes.
[1, 4]and[4, 5]share the point 4, so the test isincoming[0] <= accumulated[1]. Read the statement of each problem. A problem with half-open intervals, which exclude the end point, uses<instead.- How would you insert one new interval into a sorted list?
Insert Interval (LC 57) starts with a sorted list of disjoint intervals. Copy the intervals that end before the new one starts. Merge every interval that overlaps the new one, using the same
maxupdate. Then copy the rest. This takesO(N)time because there is no sort.
SWE Reasoning
Spot it
- The input is a list of ranges, such as meetings, bookings or time windows.
- The question asks for the combined coverage, the gaps between ranges, or a new range placed into the list.
- Ranges that overlap or touch must become one range.
- The order of the input is not guaranteed, but the answer is in order of time.
- A pair-by-pair check would take O(N^2) time. Sorting is allowed and brings the cost down to
O(N log N).
The invariant, step by step
- The list is empty, so return
[]. Otherwise sortintervalsbyiv[0], createmerged = [], and setaccumulated = intervals[0]. - For each
incomingin the rest of the sorted list, compareincoming[0]withaccumulated[1]. - If
incoming[0] <= accumulated[1], the two intervals overlap. Setaccumulated[1] = max(accumulated[1], incoming[1]). - Otherwise,
incomingstarts afteraccumulatedends. Every later interval starts even later, so appendaccumulatedtomergedand setaccumulated = incoming. mergedalways holds finished, disjoint intervals in order, andaccumulatedis the union of every interval seen since the last one was saved.- After the loop,
accumulatedis still open. Append it tomergedand returnmerged.
Traps
- Assigning the end without
max.accumulated[1] = incoming[1]moves the end back whenincominglies insideaccumulated. For[[1, 5], [2, 3], [4, 6]]it returns[[1, 3], [4, 6]]instead of[[1, 6]]. - Skipping the final flush. The last
accumulatedis never closed by the loop. Append it after the loop. - Using
<for the overlap test. Two intervals that share an end point must merge.[[1, 4], [4, 5]]becomes[[1, 5]], and<leaves two intervals. - Not sorting, or sorting by end. The one-pass argument needs the order of start times. Without it, a later interval can start before
accumulatedand the loop does not see the overlap. - Changing the caller's list.
accumulatedpoints tointervals[0], so the loop changes the input. Pass[list(iv) for iv in intervals]when the input is needed again.
Practice
Merge Intervals (LC 56)(opens leetcode.com)
You're given an array of intervals, each entry [start_i, end_i]. Fuse together every pair of intervals that overlap, then return the resulting array of non-overlapping intervals that together cover the exact same span as the original input.
Merge Intervals
intervals ➔ sort by start time ➔ merge or extend prev.end| 1 | def merge_intervals(intervals: list[list[int]]) -> list[list[int]]: |
| 2 | """Interval Merging via chronological start-time sorting. |
| 3 | Time: O(N log N) | Space: O(N) |
| 4 | """ |
| 5 | if not intervals: |
| 6 | return [] |
| 7 | |
| 8 | # 1. Sort by Start Time: |
| 9 | # Sorting puts every interval that can overlap the current one directly after it, so one |
| 10 | # left-to-right pass is enough: no interval later in the list can start earlier than this one. |
| 11 | intervals.sort(key=lambda iv: iv[0]) |
| 12 | merged: list[list[int]] = [] # merged holds finished, disjoint intervals, in order |
| 13 | accumulated = intervals[0] # accumulated is the one interval still open for absorbing overlaps |
| 14 | |
| 15 | for incoming in intervals[1:]: |
| 16 | # 2. Absorb or Close the Accumulator: |
| 17 | # incoming overlaps accumulated exactly when incoming starts at or before accumulated's end; |
| 18 | # touching at one shared point still counts as overlap. |
| 19 | if incoming[0] <= accumulated[1]: |
| 20 | accumulated[1] = max(accumulated[1], incoming[1]) # Keep the later end: a nested interval must not shrink it |
| 21 | else: |
| 22 | merged.append(accumulated) # No later interval starts before accumulated ends, so it is finished |
| 23 | accumulated = incoming # Start a new accumulator from incoming |
| 24 | |
| 25 | # 3. Flush the Last Accumulator: |
| 26 | # The loop only saves accumulated when a later interval closes it, so the final open interval is saved here. |
| 27 | merged.append(accumulated) |
| 28 | return merged |
merged holds finished, disjoint intervals in order, and accumulated is the union of every interval seen since the last one was saved.Sort by start, then keep one accumulated interval open: if incoming[0] <= accumulated[1] the two overlap, so stretch accumulated[1]; otherwise save accumulated into merged and start again from incoming. After sorting, every later interval starts at or after incoming, so once one starts past the current end, nothing later can reach back into accumulated: it is finished. The trap is the end update: use max(accumulated[1], incoming[1]), because an interval nested inside another would otherwise shrink the merged end.
See it run
Merge Intervals, step by step
accumulated [1, 5]merged none
Each column is one time point. Each row of numbers is one interval, sorted by start. A dash marks the time points the interval covers. An equals sign marks the time points covered by a saved interval in merged.
startthe start time of incomingendthe end time of incomingaccthe start time or the end time of accumulatedsavedthe start time or the end time of an interval that was just appended to merged
Sort by start. accumulated = [1, 5], the first interval.
Gotcha 1 of 4
- The trap
Gotcha 1: Setting the end to
incoming[1]withoutmaxMistakeaccumulated[1] = incoming[1]Fixaccumulated[1] = max(accumulated[1], incoming[1])What happens:
incomingcan lie completely insideaccumulated. Thenincoming[1]is smaller thanaccumulated[1]. The plain assignment moves the merged end back toincoming[1]. A later interval that overlaps the old end is then saved as a separate interval.Example: intervals = [[1, 5], [2, 3], [4, 6]]Mistake: returns [[1, 3], [4, 6]]Fix: returns [[1, 6]]
- You must keep as many intervals as possible without overlap, or remove the fewest, as in Non-overlapping Intervals (LC 435): overlapping intervals are dropped, not combined. See Interval Scheduling
- The question is how many intervals overlap at the busiest moment, as in Meeting Rooms II (LC 253), not what their union looks like. See Sweep Line
Deep Dive
Why sorting by start makes one pass enough
Two intervals overlap when each one starts at or before the other one ends. Checking every pair would take O(N^2) time. Sorting by start removes the need for that.
After the sort, the intervals come in order of start time. incoming is the next interval, and every interval after it starts at or after incoming[0]. Suppose incoming[0] > accumulated[1]. Then every later interval also starts after accumulated[1], so none of them can reach back into accumulated. It is finished, and merged.append(accumulated) is safe.
If incoming[0] <= accumulated[1], the two intervals share at least one time point. Their union is one interval, so the loop stretches accumulated[1] and keeps going.
Example: in Merge Intervals (LC 56), intervals = [[1, 3], [2, 6], [8, 10], [15, 18]] is already sorted. accumulated starts as [1, 3]. [2, 6] starts at 2, which is at most 3, so accumulated becomes [1, 6]. [8, 10] starts at 8, which is greater than 6, so [1, 6] is saved. [15, 18] starts after 10, so [8, 10] is saved. The last flush saves [15, 18]. The answer is [[1, 6], [8, 10], [15, 18]].
One trace: the end only moves right
The board replays intervals = [[1, 5], [2, 3], [4, 6], [8, 9]]. Each column is a time point. The last two rows show accumulated and merged.
[2, 3] lies inside [1, 5]. The update is max(5, 3) = 5, so the end stays 5. This is the step marked as the trap on the board. Then [4, 6] starts at 4, which is at most 5, so the end moves to 6. [8, 9] starts at 8, which is greater than 6, so [1, 6] is saved.
If the update were accumulated[1] = incoming[1], the nested [2, 3] would move the end back to 3. Then [4, 6] would start at 4, which is greater than 3, and [1, 3] would be saved as a separate interval. The wrong answer is [[1, 3], [4, 6], [8, 9]]. The right answer is [[1, 6], [8, 9]].
After the sort, max is needed only because an incoming interval can end before accumulated does. Without a nested interval, the new end is always the larger one.
The final flush and the touching case
The loop saves accumulated only when a later interval closes it. The last interval has no later interval, so nothing closes it. The line merged.append(accumulated) after the loop saves it.
Example: for [[1, 3], [2, 6], [8, 10], [15, 18]], a version without the flush returns [[1, 6], [8, 10]]. The interval [15, 18] is lost. On the board above, the flush is the step before the last step.
The test is incoming[0] <= accumulated[1], not <. In Merge Intervals (LC 56), two intervals that share one end point are merged. For [[1, 4], [4, 5]], the start 4 equals the end 4, so the answer is [[1, 5]]. With <, the two intervals stay separate.
The blueprint also changes the caller's list. accumulated = intervals[0] points to the caller's own interval, and intervals.sort reorders the caller's list. Pass a copy when the input is needed again.
The cost, and which problems fit
The sort takes O(N log N) time. The loop is one pass with O(1) work per interval, so it takes O(N) time. The total is O(N log N). merged holds up to N intervals, so the extra space is O(N).
Example: 1000 intervals take about 10000 comparisons in the sort and 999 in the loop. The sort is the cost that grows fastest.
If the input is already sorted by start, skip the sort. Insert Interval (LC 57) gives a sorted list of disjoint intervals and one new interval, so it can be solved in O(N) time with the same absorb-or-close test.
Meeting Rooms (LC 252) asks whether any two intervals overlap. Sort by start, then check each incoming[0] against the previous end. Employee Free Time (LC 759) merges the intervals of all employees, and the gaps between the merged intervals are the answer.
If the question is how many intervals are open at the same time, merging loses that count. Use the Sweep Line card for it. If the question is how many intervals to keep or remove, use the Interval Scheduling card.
60-Second Pitch
"I sort the intervals by start time. Then I keep one open interval, accumulated, and a list of finished intervals, merged. For each incoming, I compare its start with the end of accumulated. If the start is at most that end, the two overlap, so I set the end to the larger of the two ends. Otherwise accumulated is finished, because every later interval starts even later. I save it and start a new one. After the loop I save the last accumulated. The sort costs O(N log N), the pass costs O(N), and merged uses O(N) space. The cases I check are a nested interval, two intervals that touch at one point, and a single interval."
Common Questions
- Why do you sort by start time and not by end time?
Sorting by start guarantees that every later interval starts at or after
incoming[0]. Whenincomingstarts pastaccumulated[1], no later interval can reach back, soaccumulatedcan be saved. Sorted by end, a later interval could start very early and overlap an interval that was already saved.- Why is
max(accumulated[1], incoming[1])needed? incomingcan lie completely insideaccumulated. Thenincoming[1]is smaller thanaccumulated[1], and a plain assignment would move the merged end back. For[[1, 5], [2, 3], [4, 6]], that mistake saves[1, 3]instead of continuing to[1, 6].- What are the time and space complexity?
O(N log N)time, because the sort dominates and the pass isO(N). The space isO(N)formerged, plus the space the sort uses. If the input is already sorted by start, the time isO(N).- Do two intervals that only touch at one point merge?
In Merge Intervals (LC 56), yes.
[1, 4]and[4, 5]share the point 4, so the test isincoming[0] <= accumulated[1]. Read the statement of each problem. A problem with half-open intervals, which exclude the end point, uses<instead.- How would you insert one new interval into a sorted list?
Insert Interval (LC 57) starts with a sorted list of disjoint intervals. Copy the intervals that end before the new one starts. Merge every interval that overlaps the new one, using the same
maxupdate. Then copy the rest. This takesO(N)time because there is no sort.
SWE Reasoning
Spot it
- The input is a list of ranges, such as meetings, bookings or time windows.
- The question asks for the combined coverage, the gaps between ranges, or a new range placed into the list.
- Ranges that overlap or touch must become one range.
- The order of the input is not guaranteed, but the answer is in order of time.
- A pair-by-pair check would take O(N^2) time. Sorting is allowed and brings the cost down to
O(N log N).
The invariant, step by step
- The list is empty, so return
[]. Otherwise sortintervalsbyiv[0], createmerged = [], and setaccumulated = intervals[0]. - For each
incomingin the rest of the sorted list, compareincoming[0]withaccumulated[1]. - If
incoming[0] <= accumulated[1], the two intervals overlap. Setaccumulated[1] = max(accumulated[1], incoming[1]). - Otherwise,
incomingstarts afteraccumulatedends. Every later interval starts even later, so appendaccumulatedtomergedand setaccumulated = incoming. mergedalways holds finished, disjoint intervals in order, andaccumulatedis the union of every interval seen since the last one was saved.- After the loop,
accumulatedis still open. Append it tomergedand returnmerged.
Traps
- Assigning the end without
max.accumulated[1] = incoming[1]moves the end back whenincominglies insideaccumulated. For[[1, 5], [2, 3], [4, 6]]it returns[[1, 3], [4, 6]]instead of[[1, 6]]. - Skipping the final flush. The last
accumulatedis never closed by the loop. Append it after the loop. - Using
<for the overlap test. Two intervals that share an end point must merge.[[1, 4], [4, 5]]becomes[[1, 5]], and<leaves two intervals. - Not sorting, or sorting by end. The one-pass argument needs the order of start times. Without it, a later interval can start before
accumulatedand the loop does not see the overlap. - Changing the caller's list.
accumulatedpoints tointervals[0], so the loop changes the input. Pass[list(iv) for iv in intervals]when the input is needed again.