Merge overlapping intervals: [[1,3],[8,10],[2,6],[15,18]] becomes [[1,6],[8,10],[15,18]]. How do you do it, and when do touching intervals count as overlapping?
Predict first
What does the sort-and-sweep merge print for these four inputs?
func merge(_ intervals: [[Int]]) -> [[Int]] {
var out: [[Int]] = []
for iv in intervals.sorted(by: { $0[0] < $1[0] }) {
if let last = out.last, iv[0] <= last[1] {
out[out.count - 1][1] = max(last[1], iv[1])
} else {
out.append(iv)
}
}
return out
}
print(merge([[1, 3], [8, 10], [2, 6], [15, 18]]))
print(merge([[1, 4], [4, 5]]))
print(merge([[1, 10], [2, 3]]))
print(merge([]))- [[1, 6], [8, 10], [15, 18]] / [[1, 5]] / [[1, 10]] / []
- [[1, 6], [8, 10], [15, 18]] / [[1, 4], [4, 5]] / [[1, 10]] / []
- [[1, 3], [2, 6], [8, 10], [15, 18]] / [[1, 5]] / [[1, 3]] / []
Mental model. Laying strips of tape along a ruler: sort them by where they start, and each new strip either overlaps the tape you have just laid (extend it) or begins a new piece.
Sort by start, then sweep once. Keep an output list; for each interval, if its start is at or before the end of the last output interval they overlap, so extend that last end to the larger of the two ends; otherwise append the interval as a new group. Sorting dominates: O(n log n) time, O(n) for the output. Without the sort the sweep misses overlaps, because an interval far down the list could bridge two earlier ones. Note the max: a later interval can sit entirely inside the last one ([1,10] then [2,3]), and the end must not shrink.
The question hidden in the problem is the boundary rule. With iv[0] <= last[1], intervals that merely touch ([1,4] and [4,5]) merge into [1,5], as the check shows; use < if touching should stay separate. Ask, do not assume. Also handle the empty input (return an empty array), already-sorted input (still sort, or check) and intervals given as a struct or tuple rather than [Int]. The same sweep solves meeting rooms, calendar merging (see the shared-free-time question) and inserting one interval into a sorted list. Reported at Meta (anonymous, unverified).
Overlapping and touching intervals merge, an interval inside another does not shrink the end, and the empty input stays empty.
Common traps
- Not sorting first, or sorting by end instead of start.
- Setting the new end to the current interval’s end instead of the maximum, which shrinks a group when one interval contains another.
They might follow up with
- How would you insert one new interval into an already merged list? One pass, no sort: copy the ones before, merge the overlapping ones, copy the rest.
- What is the minimum number of meeting rooms? Sort starts and ends separately and sweep, or use a min-heap of end times.
Related questions
- 29.1.1 Two-sum: given an array and a target, return the indices of two elements that add up to it. How do you get…
- 29.2.8 Given two people’s busy intervals and working hours, find the time when both are free. How is it the…
- 29.1.8 When do you use a sliding window, and how do the fixed-size and variable-size versions differ?
← Two-sum: given an array and a target, return the indices of two… Write an Array extension that removes every element that appears in a… →