Given a list of intervals, merge all the overlapping ones.

What a strong answer does

I would start by making the interval contract explicit, because the code depends on it. Are the intervals already sorted, or arbitrary? Are they closed intervals like [1, 3], where both endpoints are included, or half-open intervals like [1, 3), common in scheduling? Can an interval be empty, such as [2, 2] or [2, 2), and should it be preserved? These questions sound small, but they determine whether touching endpoints merge and whether some inputs are valid at all. In an interview, asking this takes ten seconds and prevents silent assumptions.

The key move is to sort the intervals by start time. After that, the problem becomes linear because all possible future overlaps are localized. If intervals are sorted by start, then when you are considering the next interval, no later interval can start earlier than it. That means the only active interval it can affect is the merged interval you are currently building. You never need to compare it with every previous interval, because any earlier overlapping intervals have already been absorbed into the current merged range.

Then scan the sorted list while holding a current interval, often initialized to the first interval. For each next interval, compare next.start with current.end. Under closed-interval semantics, next.start <= current.end means they overlap, so the merged interval becomes [current.start, max(current.end, next.end)]. The max is important: if current is [1, 10] and next is [3, 4], the merged end must stay 10, not become 4. If there is no overlap, append current to the result and start a new current interval.

The cost is straightforward and worth stating precisely. Sorting n intervals by their start coordinate costs O(n log n). The scan afterward touches each interval once and does O(1) work per interval, so it is O(n). Overall the algorithm is O(n log n), dominated by the sort, with O(1) extra working space apart from the output if you are allowed to sort in place. If the input is guaranteed to arrive already sorted by start, then the sorting step disappears and the merge itself is simply O(n).

The edge cases are simple but should be named before they become bugs. Empty input should return an empty list, and a single interval should return itself. Fully contained intervals must not shrink the current end, which is why the max is required. Touching intervals like [1, 2] and [2, 3] merge if intervals are closed, but may not merge if the representation is half-open and the problem defines overlap as sharing positive length. That decision should match the convention agreed at the start.