Show problems as
Classic problem #57MediumArray

Insert Interval

Real-world version: Slot a New Rehearsal Block
Tracked in this browser only
Read Insert Interval on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstMerge Intervals · Arrays, animated step by step

A rehearsal room stores its booked blocks in intervals. Each block is a pair [from, to] giving the minute the block opens and the minute it closes. The blocks are listed from earliest opening to latest, and no two of them share even a single minute, not even an endpoint.

A fresh request arrives as newInterval, another [from, to] pair. Put it on the schedule. Every booked block the request runs into fuses with it into one longer block, and blocks that merely meet the request at an endpoint count as running into it.

Return the schedule after the request has been placed: a list of blocks ordered by opening minute, with no two blocks overlapping or meeting.

Examples

Example 1

Input
intervals = [[1,3],[6,9],[12,14]], newInterval = [2,7]
Output
[[1, 9], [12, 14]]

The request covers minutes 2 through 7, so it runs into [1,3] and into [6,9]; those two and the request fuse into [1,9]. The block [12,14] is left alone.

Example 2

Input
intervals = [[5,8]], newInterval = [2,5]
Output
[[2, 8]]

The request closes on the same minute the booked block opens, and meeting at an endpoint counts, so the two fuse into [2,8].

Example 3

Input
intervals = [], newInterval = [4,9]
Output
[[4, 9]]

Nothing is booked, so the schedule is the request on its own.

Example 4

Input
intervals = [[1,3],[5,6],[8,10],[14,16]], newInterval = [4,9]
Output
[[1, 3], [4, 10], [14, 16]]

The request runs into [5,6] and [8,10], and the three fuse into [4,10]. It opens at minute 4 while [1,3] closes at minute 3, so those two neither overlap nor meet, and [14,16] is untouched.

Constraints

  • 0 <= intervals.length <= 10^4
  • intervals[i].length == 2
  • 0 <= intervals[i][0] <= intervals[i][1] <= 10^5
  • intervals is ordered by opening minute, and no two blocks overlap or meet.
  • newInterval.length == 2
  • 0 <= newInterval[0] <= newInterval[1] <= 10^5

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def insert(intervals: list[list[int]], newInterval: list[int]) -> list[list[int]]:
Java
public int[][] insert(int[][] intervals, int[] newInterval)

More on the same topics