Intervals Merging and scheduling

507. Insert Interval

You are given a list intervals, where intervals[i] = [start, end], sorted by start. No two of them overlap: each interval ends before the next one starts. You are also given one more interval, newInterval.

Add newInterval to the list. If it overlaps any of the intervals, merge them all into one interval. Return the new list, sorted by start, with no two intervals overlapping.

An interval covers every number from its start to its end, both included. Two intervals overlap when they share at least one point. So [1,3] and [3,5] overlap, while [1,2] and [3,4] do not.

Example 1

Input: intervals = [[1, 2], [4, 6], [8, 10], [13, 15]] newInterval = [5, 9]

Output: [[1,2],[4,10],[13,15]]

Explanation: [5,9] overlaps [4,6] and [8,10], so the three become [4,10]. The other two intervals stay as they are.

Example 2

Input: intervals = [[1, 3], [6, 8]], newInterval = [3, 6]

Output: [[1,8]]

Explanation: [3,6] shares the point 3 with the first interval and the point 6 with the second, so all three merge.

Example 3

Input: intervals = [], newInterval = [-4, 7]

Output: [[-4,7]]

Explanation: The list is empty, so the answer holds only the new interval.

Check your understanding

Work out the answer for this input before you write any code.

intervals = [[1, 3], [5, 7], [9, 12]] newInterval = [4, 8]

Constraints

0 ≤ intervals.length ≤ 10⁵
intervals[i].length = 2 and newInterval.length = 2
-10⁹ ≤ start ≤ end ≤ 10⁹ for every interval, newInterval included
intervals is sorted by start, and intervals[i][1] < intervals[i + 1][0].

Clarifying questions

What you would ask an interviewer before writing any code.