Fitting In a New Booking

Medium

A meeting room schedule is a list bookings where bookings[i] = [start, end] is a busy time segment including both ends. The segments are sorted by start and do not overlap. A new booking extra = [start, end] arrives. Add it to the schedule: every segment that overlaps it or touches it at even one point merges with it into a single segment. Return the new schedule, still sorted and without overlaps. You don't have to change bookings in place; returning a new list is fine.

Example 1

bookings=[[2, 4], [9, 12], [15, 20]], extra=[5, 10] → [[2, 4], [5, 12], [15, 20]]

The new booking [5, 10] overlaps [9, 12] and merges into [5, 12]; it does not overlap [2, 4].

Example 2

bookings=[[1, 3], [6, 8]], extra=[3, 6] → [[1, 8]]

Segments that share an endpoint merge, so everything becomes [1, 8].

Example 3

bookings=[], extra=[7, 7] → [[7, 7]]

There were no bookings, so only the new one remains.

Constraints

0 ≤ len(bookings) ≤ 10⁴
0 ≤ start ≤ end ≤ 10⁵ for every segment and for extra
Each segment in bookings ends before the next one starts

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array

Similar problems

Two Boards Holding Water Medium Zero-Sum Triples Medium Triple Sum Nearest the Target Medium Four Numbers to a Target Medium Next Arrangement in Order Medium

Input

bookings=[[2, 4], [9, 12], [15, 20]], extra=[5, 10]

Expected

[[2, 4], [5, 12], [15, 20]]

Run checks the first 3 tests in your browser. Submit checks all 169 tests on the server, hidden ones included.