How do you merge overlapping intervals, and what are the edge cases?

AlgorithmsJunior

In shortSort by start, then walk once, comparing each interval with the last merged one; if it overlaps, extend the end to the larger end, otherwise start a new interval. O(n log n).

Model answer

Sort by start. After that, an interval can only overlap the last one you’ve merged.
Walk once. If the current interval starts at or before the last merged end, they overlap: set the end to max(last end, current end). Otherwise, append it as a new interval.

fun merge(intervals: Array<IntArray>): List<IntArray> {
    val merged = mutableListOf<IntArray>()
    for (cur in intervals.sortedBy { it[0] }) {
        val last = merged.lastOrNull()
        if (last != null && cur[0] <= last[1]) last[1] = maxOf(last[1], cur[1])
        else merged.add(cur.copyOf())
    }
    return merged
}

Edge cases worth naming: nested intervals ([1, 10] and [2, 3], the reason for max), touching intervals ([1, 4] and [4, 5]: merged if closed, separate if half-open; ask), an empty input, and comparator overflow on the JVM if you sort with a[0] - b[0]. Sorting is O(n log n), the walk O(n).

What they're looking for

Sorting by start, comparing only with the last merged interval, using max for the end, and asking whether touching intervals count as overlapping.

Common mistakes

Setting the end to the current interval's end instead of the maximum (breaks on nested intervals).
Comparing every pair, O(n²).
Not clarifying closed versus half-open intervals.

How do you merge overlapping intervals, and what are the edge cases?

Model answer

What they're looking for

Common mistakes

More algorithms questions