Merge all overlapping intervals in a slice of [start, end] pairs
Given a slice of intervals [][]int, where each element is a [start, end] pair, return a new slice in which every set of overlapping intervals has been merged into one. Touching intervals (where one ends exactly where the next begins) count as overlapping. Target O(n log n) time.
func merge(intervals [][]int) [][]int {
// your code here
}Write the implementation.
Sort the intervals by start time, then sweep once: keep the last interval in the result; for each next interval, if its start ≤ the last interval's end they overlap, so extend the last end to max(lastEnd, end); otherwise append it as a new interval. The result is the minimal set of non-overlapping intervals. O(n log n) for the sort, O(n) for the sweep.
- ✗Skipping the sort and assuming a single unsorted pass merges everything
- ✗Comparing only adjacent originals, missing a transitive chain merged through a running end
- ✗Taking the intersection instead of the union when extending the merged interval
- →Why is touching (
start == lastEnd) treated as overlapping here, and when might you exclude it? - →How would you insert one new interval into an already-merged, sorted list in O(n)?
Task
Merge all overlapping [start, end] intervals. Touching intervals count as overlapping.
func merge(intervals [][]int) [][]int {
if len(intervals) == 0 {
return nil
}
sort.Slice(intervals, func(i, j int) bool {
return intervals[i][0] < intervals[j][0]
})
res := [][]int{intervals[0]}
for _, in := range intervals[1:] {
last := res[len(res)-1]
if in[0] <= last[1] { // overlap (touching counts)
if in[1] > last[1] {
last[1] = in[1] // extend the end
}
} else {
res = append(res, in)
}
}
return res
}How it works
Sorting by start makes overlapping intervals adjacent. A single pass then keeps the last interval of the result:
- if the next interval's start
in[0] <= last[1], they overlap, so extend the last end tomax(last[1], in[1]); - otherwise the next interval is disjoint from everything before — append it as new.
last is a slice aliasing an element of res, so last[1] = in[1] edits the result in place. The sort is O(n log n), the sweep O(n).
