Middle · Algorithms
Merge intervals: define whether touching endpoints overlap
How do you normalize overlapping closed intervals efficiently?
Try explaining this aloud before opening the answer. State your assumptions and trace a boundary case.
ALGORITHM LAB · STEP THROUGH THE INVARIANT
[(1, 4), (2, 3), (4, 6), (9, 10)]
Sort by start and end
Sort a copy so callers keep their input order.
Computed traces for these inputs. Indexes identify cell positions; active cells are labeled as well as highlighted. Compare a boundary case using the scenario selector. No code is sent to a server.
type Interval struct{ Start, End int }
// Closed intervals; caller validates Start<=End. Does not mutate input.
func MergeIntervals(input []Interval) []Interval {
xs := append([]Interval(nil), input...)
sort.Slice(xs, func(i, j int) bool {
if xs[i].Start == xs[j].Start {
return xs[i].End < xs[j].End
}
return xs[i].Start < xs[j].Start
})
var out []Interval
for _, x := range xs {
if len(out) == 0 || x.Start > out[len(out)-1].End {
out = append(out, x)
continue
}
if x.End > out[len(out)-1].End {
out[len(out)-1].End = x.End
}
}
return out
}Reveal a strong answer
State the endpoint convention first. This example uses closed intervals [start,end], so [1,3] and [3,5] overlap. Half-open time ranges [start,end) may use another adjacency rule. Reject reversed endpoints before calling the helper.
Sort by start, then end. Maintain a disjoint ordered output. If the next start is at most the last end, extend that last end to the maximum; otherwise append a new interval. Do not replace a long containing interval with a shorter nested one.
Copy the input before sorting when callers retain its order. Test empty input, a contained interval, equal boundaries and already separated ranges. Go integer width and domain-specific timestamp units remain part of the input contract.
Common trap
Confusing closed and half-open endpoints, or shrinking an interval when a contained interval arrives.
Complexity & use
O(n log n) time for sorting and O(n) storage to preserve caller input; the merge scan itself is linear.
Try it
Merge [1,4], [2,3], [4,6] and [9,10] under closed-interval semantics.
Worked solution
The first two retain [1,4], because the second is contained. The touching [4,6] extends it to [1,6]. The gap before 9 starts another interval, producing [1,6] and [9,10]. The original input order remains unchanged.
Change the constraint
How would your comparison change if touching half-open intervals must remain separate?
How did you do?
Self-assessment, not a compiler pass or interview score. Explain the reasoning unaided before marking understood.
Not marked. Progress stays on this browser, separate from course completion.
Primary references
Checked 2026-10-27. Use documentation for your pinned runtime, driver and tool version.