How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

Merge overlapping intervals | Amazon Coding Question

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].

Input: []

Expected Output: []

Explanation: Empty input returns an empty list.

Input: [[1, 4]]

Expected Output: [[1, 4]]

Explanation: A single interval is returned unchanged.

Input: [[1, 10], [2, 3], [4, 5]]

Expected Output: [[1, 10]]

Explanation: Both [2,3] and [4,5] are fully nested inside [1,10], so everything collapses to [1,10].

Input: [[-5, -1], [-3, 0], [2, 4]]

Expected Output: [[-5, 0], [2, 4]]

Explanation: Negative coordinates: [-5,-1] and [-3,0] overlap and merge to [-5,0]; [2,4] is separate.

Input: [[3, 5], [1, 2], [6, 8], [2, 3]]

Expected Output: [[1, 5], [6, 8]]

Explanation: Unsorted input; after sorting, [1,2],[2,3],[3,5] chain-merge into [1,5] via boundary touches and overlap.

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

Expected Output: [[1, 4], [5, 6]]

Explanation: There is a gap between 4 and 5 (5 > 4), so the intervals stay separate.

Input: [[2, 2], [2, 5]]

Expected Output: [[2, 5]]

Explanation: Zero-length interval [2,2] merges with [2,5] since 2 <= 2.

Hints

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.
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).
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.

Quick Overview