Slot a New Booking Into a Sorted Calendar

Medium20–25 min

Topics

GreedyIntervalsArray

Companies

GoogleAmazonLinkedIn

A calendar holds booked time ranges in sorted order; no two of them overlap or touch. A new booking arrives. Add it to the calendar, combining it with every existing range it overlaps (ranges that merely touch at a single point also count as overlapping), and return the updated calendar, still sorted.

You could throw everything into a list, sort it and merge — but the calendar is already sorted. Because of that, the ranges fall into three groups around the new booking (entirely before it, overlapping it, entirely after it), and one linear pass is enough.

Test Case 1:

Input:calendar = [[2, 4], [6, 7], [9, 12], [14, 16], [19, 20]], newBooking = [5, 10]

Output:[[2, 4], [5, 12], [14, 16], [19, 20]]

Explanation:[5, 10] overlaps [6, 7] and [9, 12], so the three merge into [5, 12]. [2, 4] ends before 5 and [14, 16] starts after 12, so they are untouched.

Test Case 2:

Input:calendar = [[5, 8]], newBooking = [8, 10]

Output:[[5, 10]]

Explanation:The new booking starts exactly where [5, 8] ends; touching counts as overlapping, so they merge.

Test Case 3:

Input:calendar = [[5, 8]], newBooking = [1, 3]

Output:[[1, 3], [5, 8]]

Explanation:The new booking is entirely before the only existing one: no merge, it just goes first.

Constraints

◆1 ≤ calendar.length ≤ 12; each entry is [start, end] with 0 ≤ start < end ≤ 60
◆The calendar is sorted by start, and its entries never overlap or touch (each start is strictly greater than the previous end)
◆newBooking is [start, end] with 0 ≤ start < end ≤ 60
◆Ranges that overlap — including ranges that touch at a single point — are combined. Return the calendar after adding newBooking, still sorted and with no overlapping or touching ranges

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Add It, Then Sort and Merge Everything

Brute

Ignore the fact that the calendar is already in order. Put the new booking in with the rest, sort all the ranges by start, and run the standard combine- overlapping-ranges sweep: keep a current range, extend it while the next range starts at or before its end, and store it when a gap appears. It is correct and short, but it pays for a full sort of ranges that were already sorted.

TimeO(n log n)

SpaceO(n)

Java

Try it out

class Solution {
    public int[][] slotBooking(int[][] calendar, int[] newBooking) {
        List<int[]> all = new ArrayList<>();
        for (int[] range : calendar) all.add(new int[]{range[0], range[1]});
        all.add(new int[]{newBooking[0], newBooking[1]});
        all.sort((a, b) -> a[0] - b[0]);
        List<int[]> result = new ArrayList<>();
        int[] current = all.get(0);
        for (int k = 1; k < all.size(); k++) {
            int[] next = all.get(k);
            if (next[0] <= current[1]) {
                current[1] = Math.max(current[1], next[1]);
            } else {
                result.add(current);
                current = next;
            }
        }
        result.add(current);
        return result.toArray(new int[0][]);
    }
}

Optimal — One Pass: Copy Before, Merge Overlaps, Copy After

Optimal

Because the calendar is sorted and disjoint, the ranges split into three runs relative to the new booking. First run: ranges that end strictly before the new booking starts — copy them unchanged. Second run: ranges that start at or before the new booking's end — they all overlap it, so widen the new booking to cover each one (smaller start, larger end). Third run: everything else — copy unchanged. Insert the widened booking between the runs. Each range is looked at once, so the work is linear with no sorting.

TimeO(n)