Insert Interval
Medium · Intervals
You are given a list of non-overlapping intervals sorted by their start values, and a single new interval to add. Insert the new interval into the list, merging it with any existing intervals it overlaps or touches, and return the resulting list of intervals still sorted by start value. Two intervals overlap if they share at least one point.
Examples
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Why: The new interval [2,5] overlaps [1,3], so they merge into [1,5]; [6,9] stays separate since it doesn't touch [1,5].Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Why: The new interval [4,8] overlaps [3,5], [6,7], and [8,10], merging them all into [3,10]; the untouched intervals stay in place.Input: intervals = [], newInterval = [5,7]
Output: [[5,7]]
Why: With no existing intervals, the new one is simply added by itself.Constraints
0 <= intervals.length <= 10^4, intervals[i].length == 2, 0 <= intervals[i][0] <= intervals[i][1] <= 10^5, intervals is sorted by start and non-overlapping, newInterval.length == 2, 0 <= newInterval[0] <= newInterval[1] <= 10^5
Practise it by voice
Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.
This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Insert Interval. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.