DSA · Intervals · #86
Insert Interval
Module 67 · difficulty 3/5·⏱ 30:00starts on first keystroke
You are given an array `intervals` of non-overlapping intervals sorted in ascending order by start, where `intervals[i] = [start_i, end_i]`. You are also given a single interval `newInterval = [start, end]`. Implement `insert(intervals, newInterval)` that inserts `newInterval` into `intervals` so the result is still sorted by start and contains no overlapping intervals (merging where necessary). Return the resulting array of intervals. Two intervals are considered overlapping if they merely touch (e.g. `[1,2]` and `[2,3]`).
Examples
intervals = [[1,3],[6,9]], newInterval = [2,5]→[[1,5],[6,9]]— [2,5] overlaps [1,3], so they merge into [1,5].intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]→[[1,2],[3,10],[12,16]]— [4,8] overlaps [3,5],[6,7],[8,10], merging into [3,10].intervals = [], newInterval = [5,7]→[[5,7]]— Inserting into an empty list.
Constraints
- · 0 <= intervals.length <= 10^4
- · intervals[i].length == 2
- · 0 <= start_i <= end_i <= 10^5
- · intervals is sorted by start_i in ascending order
- · newInterval.length == 2
- · 0 <= start <= end <= 10^5
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.