intervals · Problem 1 of 2

Insert Interval

medium
Google logoGoogle
Meta logoMeta
Amazon logoAmazon
Microsoft logoMicrosoft
LinkedIn logoLinkedIn

You are given an array of non-overlapping intervals intervals where intervals[i] = [start, end] sorted in ascending order by start time. You are also given an interval newInterval = [start, end].

Insert newInterval into intervals such that intervals is still sorted in ascending order and contains no overlapping intervals (merging overlapping intervals if necessary).

insertInterval([[1, 3], [6, 9]], [2, 5]) 
  -> [[1, 5], [6, 9]]

insertInterval([[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], [4, 8]) 
  -> [[1, 2], [3, 10], [12, 16]]

Your solution

Runs your code and animates it without grading anything. Change the input to see what it does on a case the tests do not cover.

Running is free — Submit is what records it. Or press ⌘↩

Tests

4 cases, 1 hidden
calltypeexpectedresult
insertInterval([[1,3],[6,9]], [2,5])single overlap[[1,5],[6,9]]—
insertInterval([[1,2],[3,5],[6,7],[8,10],[12,16]], [4,8])multi interval merge[[1,2],[3,10],[12,16]]—
insertInterval([[5,7]], [1,2])insert at beginning[[1,2],[5,7]]—
withheldhiddenwithheld—

Hidden cases run too — their inputs aren't listed here, so aim for a general solution rather than one fitted to the cases above.

Complexity

target time
O(n)
target space
O(n) for result array

Single pass through the intervals array without needing any re-sorting.

Hints

Stuck? Hints open one at a time, each giving a little more away.

4 hints left