‹ DS&A interview · Socratic
DSA · Intervals / sorting · #16

Merge Intervals

Module 19 · difficulty 3/5·⏱ 30:00starts on first keystroke

Given an array of intervals where `intervals[i] = [start_i, end_i]`, merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input. Return them sorted by start.

Examples
  • intervals = [[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]] — [1,3] and [2,6] overlap → [1,6]
  • intervals = [[1,4],[4,5]] → [[1,5]] — touching endpoints merge
  • intervals = [[1,4]] → [[1,4]]
Constraints
  • · 1 <= intervals.length <= 10^4
  • · intervals[i].length == 2
  • · 0 <= start_i <= end_i <= 10^4
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.