CodePark/ problems / Insert a New Range
START PRACTICINGPRACTICE
Coding problem · Data structures and algorithms › Sorting and intervals

Insert a New Range

mediumabout 20 minutes in an interview

intervals is a list of ranges [start, end]. They are already in order by start, and none of them overlap. You also get one new range, newInterval. Put it into the list and return the updated list.

  • If the new range overlaps some existing ranges, join them all into one range.
  • The returned list must still be in order by start, with no overlaps.
  • Ranges that touch count as overlapping. For example, adding [3, 6] to [[1, 3], [6, 8]] gives [[1, 8]].
  • intervals can be empty. Every range has start <= end.
  • Aim for O(n) time: one walk over the list, with no sorting.
Input: intervals = [[1, 2], [4, 6], [8, 9], [11, 14]], newInterval = [5, 8] Output: [[1, 2], [4, 9], [11, 14]][5, 8] overlaps [4, 6] and touches [8, 9]. So all three become [4, 9].
Input: intervals = [[1, 2], [8, 9]], newInterval = [4, 5] Output: [[1, 2], [4, 5], [8, 9]]