Topic · IntervalsMedium
Insert Interval
Understand the problem
Given a list of intervals sorted ascending by start and non-overlapping, plus a new interval newInterval.
Insert newInterval, merging if they overlap, and keep the result sorted and non-overlapping.
ts
intervals = [[1,3],[6,9]], newInterval = [2,5]
output = [[1,5],[6,9]] // [2,5] overlaps [1,3] → merged into [1,5]Since the input is already sorted, we scan once in 3 phases: the intervals that lie entirely before newInterval, the intervals that overlap newInterval (merged together), then the rest, which lie after.
Basic approach
O(n log n) time, O(n) spacets
function insertNaive(intervals: number[][], newInterval: number[]): number[][] {
const all = [...intervals, newInterval]
all.sort((a, b) => a[0] - b[0]) // input is already sorted → re-sorting is redundant
// ... then run the exact Merge Intervals algorithm on 'all'
return mergeIntervals(all)
}Why this approach is slow:
This approach stuffs newInterval in, re-sorts, and merges like the Merge Intervals problem.
Correct but it wastes the sorting step since the input is already sorted — a linear scan costs only O(n).
Unlock the optimal solution, the step-by-step trace and related questions
See the full step-by-step trace, Big-O and edge cases.