Merge Intervals
You get a set of intervals, each a range of whole numbers from a start to an end. Merge every group of overlapping intervals into one interval that covers the whole group, and return the merged intervals sorted by start. Intervals that only touch, like [1, 4] and [4, 5], count as overlapping.
The intervals come in as two arrays of the same length: interval i is [starts[i], ends[i]]. You return a 2D array, a list of [start, end] pairs.
Function
- startsinteger-array
- the start of each interval
- endsinteger-array
- the end of each interval, at the same index as its start
- Returnsinteger-2d-array
- the merged intervals as [start, end] pairs, sorted by start
Constraints
1 ≤ starts.length == ends.length ≤ 1040 ≤ starts[i] ≤ ends[i] ≤ 104- The intervals arrive in any order.
- Intervals that only touch at an end count as overlapping.
Examples
- Input
- starts = [5, 1, 12, 3]ends = [7, 4, 14, 6]
- Output
- [[1, 7], [12, 14]]
- Explanation
- In order of start, [1, 4] overlaps [3, 6], which overlaps [5, 7], so the three become [1, 7]. [12, 14] starts after 7 and stays on its own.
- Input
- starts = [6, 1]ends = [9, 6]
- Output
- [[1, 9]]
- Explanation
- The intervals are [6, 9] and [1, 6]. They share the point 6, and touching counts as overlapping, so they merge into [1, 9].
Follow-up
The intervals arrive already merged and sorted by start, and you must add one new interval. Can you return the merged list in O(n) time, without sorting again?
Hints
Open them one at a time. Each one gives away a little more.
Pair every start with its end first, so you work with whole intervals instead of two separate arrays.
Sort the intervals by start. After that, an interval can only overlap the group right before it, never one further back.
Walk the sorted intervals while holding the last merged one. If the next start is less than or equal to its end, set its end to the larger of the two ends. Otherwise that group is finished and the next interval opens a new one.
Solution
Merging pairs in any order needs repeated passes, because each merge widens an interval and lets it reach intervals you already checked. Sort by start instead. Then an interval can only overlap the group you are building, and one pass finishes the job.
Merge overlapping pairs until nothing changes
Correct, but does not finish on the largest tests
Intuition
Intervals [a, b] and [c, d] overlap when c ≤ b and a ≤ d, and [min(a, c), max(b, d)] covers both. Each merge removes one interval, so the process stops, and once a full pass finds no overlap, no two intervals left share a point. One pass is not enough: a merged interval is wider and can now reach an interval its smaller part was compared with earlier in the pass.
A pass compares about n²/2 pairs and you may need up to n passes: O(n³). One pass over 10^4 intervals is already 5 × 10^7 comparisons.
Algorithm
- Copy
startsandends, and keep a countnof live intervals. - Compare each interval
iwith every later intervalj. If they overlap, stretchito coverj, move the last live interval into slotjand lowernby one. - After a merge, check slot
jagain, since a different interval sits there now. - Repeat passes until one makes no merge.
- Pair each live start with its end, sort the pairs by start and return them.
def mergeIntervals(starts, ends):
s = list(starts)
e = list(ends)
n = len(s)
changed = True
while changed:
changed = False
i = 0
while i < n:
j = i + 1
while j < n:
if s[j] <= e[i] and s[i] <= e[j]:
# Intervals i and j overlap: interval i absorbs interval j.
s[i] = min(s[i], s[j])
e[i] = max(e[i], e[j])
# Move the last interval into slot j and drop the last slot.
n -= 1
s[j] = s[n]
e[j] = e[n]
changed = True
else:
j += 1
i += 1
return sorted([s[k], e[k]] for k in range(n))Sort by start and sweep once
Intuition
After sorting by start, the next interval starts no earlier than anything in the last group, which ends at e. If its start is at most e, it overlaps or touches the group and joins it, and e becomes the larger of the two ends. If its start is past e, no later interval can reach back into the group either, because later intervals start further right. The group is finished, and the interval opens a new one.
Sorting costs O(n log n) and the sweep visits each interval once. Groups close from left to right, so the result comes out sorted by start.
Algorithm
- Pair each start with its end: interval
iis[starts[i], ends[i]]. - Sort the pairs by start.
- Walk the sorted pairs. If the result is empty, or the pair starts after the end of the last merged interval, append the pair as a new interval.
- Otherwise set the end of the last merged interval to the larger of its end and the pair's end.
- Return the merged list.
def mergeIntervals(starts, ends):
intervals = sorted(zip(starts, ends))
merged = []
for start, end in intervals:
if merged and start <= merged[-1][1]:
if end > merged[-1][1]:
merged[-1][1] = end
else:
merged.append([start, end])
return merged
Pitfalls and edge cases
- Comparing with
<instead of≤. Touching intervals such as[1, 4]and[4, 5]must merge. - Setting the end to the new interval's end instead of the larger of the two.
[1, 10]followed by[2, 3]must stay[1, 10]. - Sorting
startson its own and then readingendsat the new positions, so a start gets another interval's end. Pair them first, or sort indices. - Comparing with the previous input interval instead of the last merged one. In
[1, 10],[2, 3],[4, 5], the third interval lies inside[1, 10]though it does not touch[2, 3]. - In C, not setting
*returnSizeto the number of merged intervals and every column size to 2.
Frequently asked questions3
What is the time complexity of Merge Intervals?
The sort and sweep solution runs in O(n log n) time for n intervals: the sort costs O(n log n) and the sweep O(n). It uses O(n) extra space for the sorted pairs and the result.
Why sort the intervals by start and not by end?
Sorted by start, an interval can only overlap the group you are building, so one comparison with that group's end decides everything. Sorted by end, a later interval can start before groups you already closed: [5, 6] comes before [1, 10], and a forward sweep would wrongly keep 5 as the start.
Can you merge intervals without extra space?
Yes, if you may change the input. Sort the intervals in place, then write each merged interval over the front of the same array and keep the index of the last one written. The time stays O(n log n), and the only extra space is what your language's sort uses.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
def mergeIntervals(starts, ends):
# Write code hereTest #1
Test #2
Arguments
starts = [5, 1, 12, 3] ends = [7, 4, 14, 6]
Expected Output
[[1, 7], [12, 14]]