Quick Overview

Merge overlapping intervals evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Merge overlapping intervals

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Given a list of half-open numeric intervals [start, end), merge all overlapping or contiguous intervals and return a list of non-overlapping intervals sorted by start. Analyze time and space complexity and cover edge cases such as empty input, nested intervals, and negative coordinates.

Quick Answer: Merge overlapping intervals evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Given a list of half-open numeric intervals `[start, end)`, merge all overlapping or contiguous intervals and return a list of non-overlapping intervals sorted by start. Because the intervals are half-open, two intervals are mergeable when `next.start <= current.end` — this covers both true overlaps (`next.start < current.end`) and contiguous intervals that touch exactly at the boundary (`next.start == current.end`). Implement `merge(intervals)` returning the merged list. Each interval is a two-element list `[start, end]`. The returned intervals must be sorted by start and non-overlapping. Examples: - `merge([[1,3],[2,6],[8,10],[15,18]])` -> `[[1,6],[8,10],[15,18]]` - `merge([[1,4],[4,5]])` -> `[[1,5]]` (contiguous, touch at the boundary) - `merge([])` -> `[]` Edge cases to handle: empty input, a single interval, fully nested intervals, duplicate intervals, negative coordinates, and zero-length intervals.

Constraints

  • 0 <= number of intervals <= 10^5
  • Each interval is [start, end) with start <= end
  • -10^9 <= start <= end <= 10^9
  • Intervals may be given in any order (unsorted)
  • Half-open semantics: intervals touching exactly at a boundary (next.start == current.end) are merged

Examples

Input: [[1, 3], [2, 6], [8, 10], [15, 18]]

Expected Output: [[1, 6], [8, 10], [15, 18]]

Explanation: [1,3] and [2,6] overlap (2 < 3) and merge into [1,6]; the others are disjoint.

Input: [[1, 4], [4, 5]]

Expected Output: [[1, 5]]

Explanation: Half-open intervals touching at boundary 4 (next.start == current.end) are contiguous and merge into [1,5].

Hints

  1. Sort the intervals by their start coordinate first — this guarantees any interval that overlaps the current merged block starts at or after the current block's start.
  2. Walk through the sorted list maintaining a single 'current' merged interval. For each next interval, if next.start <= current.end the two overlap or touch, so extend current.end = max(current.end, next.end).
  3. If next.start > current.end there is a gap, so finalize the current interval and begin a new one. Handle the empty-input case up front by returning an empty list.

Loading coding console...