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.
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.
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
- 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.
Community answers
Answer by subnr01
#include
#include
#include
using Interval = std::pair; // (start, end)
std::vector mergeHalfOpen(std::vector intervals) {
if (intervals.empty()) return {};
// Assumes valid intervals: start <= end. (See notes below for handling invalid/empty.)
std::sort(intervals.begin(), intervals.end(),
[](const Interval& a, const Interval& b) {
if (a.first != b.first) return a.first < b.first;
return a.second < b.second;
});
std::vector merged;
long long curS = intervals[0].first;
long long curE = intervals[0].second;
for (size_t i = 1; i < intervals.size(); ++i) {
long long s = intervals[i].first;
long long e = intervals[i].second;
if (s <= curE) { // overlap or contiguous
if (e > curE) curE = e; // extend end
} else {
merged.push_back({curS, curE});
curS = s;
curE = e;
}
}
merged.push_back({curS, curE});
return merged;
}