Insert Interval

MediumIntervalsinterval merge

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given a list of intervals that is already sorted by start value and contains no overlaps. Each entry is a pair [start, end] describing a closed range. You are also given a single newInterval [start, end] that must be inserted into the list. Return a new list of intervals that is still sorted by start value and still has no overlaps, merging any intervals that overlap with newInterval (or with each other after the insertion). Two intervals are considered to overlap if they share at least one point, including touching only at an endpoint (for example [1, 3] and [3, 5] overlap and should merge into [1, 5]). The original intervals list does not change other than the merging required to accommodate newInterval.

Examples

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
The new interval [2,5] overlaps [1,3], so they merge into [1,5]. The interval [6,9] is untouched.
Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
[4,8] overlaps [3,5], [6,7], and [8,10], merging them all into [3,10].
Input: intervals = [], newInterval = [5,7]
Output: [[5,7]]
With no existing intervals, the new interval is simply the entire result.

Constraints

  • `0 <= intervals.length <= 10^4`
  • `intervals[i].length == 2` and `newInterval.length == 2`
  • `0 <= start <= end <= 10^5` for every interval
  • `intervals` is sorted by start value in ascending order and has no overlapping intervals

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.