IntermediateArraysGreedy
Merge Intervals
Problem
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. Two intervals that merely touch (one ends where the other starts) are considered overlapping.
Constraints
- 1 ≤ n ≤ 10^4
- 0 ≤ start_i ≤ end_i ≤ 10^4
- input is not necessarily sorted
Examples
in: intervals = [[1,3],[2,6],[8,10],[15,18]]
out: [[1,6],[8,10],[15,18]]
[1,3] and [2,6] overlap and merge into [1,6].
in: intervals = [[1,4],[4,5]]
out: [[1,5]]
Touching intervals merge.
What this tests
- Recognising that sorting by start turns a pairwise problem into a linear sweep
- Correct overlap condition (closed vs open endpoints)
- Maintaining a "current merged interval" invariant
- Edge cases with containment and touching endpoints
Problem ClarificationPattern RecognitionImplementationEdge CasesComplexity Analysis
Progressive hints
Choose how much help you want. Each hint reveals a little more; the pattern is not named until hint 2.
Hint 1Direction
Hint 2Pattern
Hint 3Data structure
Hint 4Algorithm
Hint 5Pseudocode
Solution
Solve in your language
The editor, starter code and solution adapt to the language you pick — C++, JavaScript, TypeScript or Python.
Solve in
Candidate thinking
How a strong candidate reasons through this problem, step by step.
Try the problem yourself first (or run the mock interview), then compare your process against a strong candidate's.
Follow-up engine
Requirements change; so does the right algorithm.
F1
Insert one new interval into an already merged, sorted list (Insert Interval).
F2
Find the minimum number of intervals to remove so the rest are non-overlapping.
F3
Given meeting intervals, how many rooms are needed (Meeting Rooms II)?
F4
Intervals arrive in a stream and you need to report the merged set after every insertion.