My Calendar III

Hard
1439.

My Calendar III

My Calendar III is a hard coding problem on binary search, prefix sum and ordered set, asked in Amazon and Google interviews.

A calendar receives events one at a time. Each event bookings[i] = [startTime, endTime] occupies the half-open interval [startTime, endTime). Events are always accepted, even when they overlap.

A k-booking happens when some moment is covered by k events at once. After each event is added, report the largest k for which a k-booking exists among all events added so far.

Return the array of those answers, one per event, in order. (On LeetCode this is the book method of a MyCalendarThree class called once per event.)

Example 1

Input
bookings = [[1,5],[3,8],[4,6],[8,9]]
Output
[1,2,3,3]
Explanation
[3,5) is double-booked after the second event and [4,5) triple-booked after the third; [8,9) only touches [3,8).

Example 2

Input
bookings = [[10,20],[50,60],[10,40],[5,15],[5,10],[25,55]]
Output
[1,1,2,3,3,3]

Constraints

  • 1 <= bookings.length <= 400
  • 0 <= startTime < endTime <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} bookings
 * @return {number[]}
 */
var myCalendarThree = function(bookings) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

My Calendar III — Solution in Python, Java & C++

My Calendar III solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

My Calendar III is a hard coding problem on binary search, prefix sum and ordered set, asked in Amazon and Google interviews.

Problem statement

A calendar receives events one at a time. Each event bookings[i] = [startTime, endTime] occupies the half-open interval [startTime, endTime). Events are always accepted, even when they overlap.

A k-booking happens when some moment is covered by k events at once. After each event is added, report the largest k for which a k-booking exists among all events added so far.

Return the array of those answers, one per event, in order. (On LeetCode this is the book method of a MyCalendarThree class called once per event.)

Example 1

Input: bookings = [[1,5],[3,8],[4,6],[8,9]]
Output: [1,2,3,3]
Explanation: [3,5) is double-booked after the second event and [4,5) triple-booked after the third; [8,9) only touches [3,8).

Example 2

Input: bookings = [[10,20],[50,60],[10,40],[5,15],[5,10],[25,55]]
Output: [1,1,2,3,3,3]

Constraints

  • 1 <= bookings.length <= 400
  • 0 <= startTime < endTime <= 10^9

Hints for My Calendar III

  1. Hint 1

    The overlap count only changes at an event's start or end, so only those coordinates matter.

  2. Hint 2

    Compress all startTime and endTime values into indices; the gaps between consecutive coordinates are the elementary segments.

  3. Hint 3

    Keep a counter per elementary segment. Adding an event increments the segments it covers; the answer is the running maximum of all counters.

How to solve My Calendar III

With at most 400 events, coordinate compression turns the timeline into at most 799 elementary segments. An event covers a contiguous range of them, so adding it is a range increment, and the answer is the largest counter ever reached.

Approach

  1. Collect every start and end, sort, and deduplicate into xs.
  2. Keep cover[s] for each segment [xs[s], xs[s+1]) and best = 0.
  3. For each event, find the indices of its start and end in xs (binary search), increment cover over that index range and update best with each new value.
  4. Append best after every event.

Why it works

Between two consecutive coordinates no event begins or ends, so every moment of a segment is covered by the same set of events, and cover[s] counts exactly that set. The overlap maximum over all time is therefore the maximum counter, and since counters only grow, keeping a running maximum is enough.

Complexity

  • Time — O(n^2) after the O(n log n) compression
  • Space — O(n)

Pitfalls

  • Intervals are half-open: an event ending at 8 and one starting at 8 do not overlap.
  • Compress over all events up front (they are all known), or use an ordered map of +1/-1 deltas if they arrive online.
  • A segment tree with lazy range add answers each event in O(log n) if the number of events is large.

Reference solution

Python

from typing import List
from bisect import bisect_left

def myCalendarThree(bookings: List[List[int]]) -> List[int]:
    xs = sorted(set(x for b in bookings for x in b))
    cover = [0] * len(xs)  # cover[s] counts events over [xs[s], xs[s + 1])
    best = 0
    out = []
    for start, end in bookings:
        for s in range(bisect_left(xs, start), bisect_left(xs, end)):
            cover[s] += 1
            best = max(best, cover[s])
        out.append(best)
    return out

Java

public static int[] myCalendarThree(int[][] bookings) {
    int n = bookings.length;
    int[] all = new int[2 * n];
    for (int i = 0; i < n; i++) {
        all[2 * i] = bookings[i][0];
        all[2 * i + 1] = bookings[i][1];
    }
    int[] xs = Arrays.stream(all).sorted().distinct().toArray();
    int[] cover = new int[xs.length]; // cover[s] counts events over [xs[s], xs[s + 1])
    int best = 0;
    int[] out = new int[n];
    for (int t = 0; t < n; t++) {
        int a = Arrays.binarySearch(xs, bookings[t][0]);
        int b = Arrays.binarySearch(xs, bookings[t][1]);
        for (int s = a; s < b; s++) best = Math.max(best, ++cover[s]);
        out[t] = best;
    }
    return out;
}

C++

vector<int> myCalendarThree(vector<vector<int>>& bookings) {
    vector<int> xs;
    for (auto& b : bookings) {
        xs.push_back(b[0]);
        xs.push_back(b[1]);
    }
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    vector<int> cover(xs.size(), 0); // cover[s] counts events over [xs[s], xs[s + 1])
    int best = 0;
    vector<int> out;
    for (auto& b : bookings) {
        int a = lower_bound(xs.begin(), xs.end(), b[0]) - xs.begin();
        int e = lower_bound(xs.begin(), xs.end(), b[1]) - xs.begin();
        for (int s = a; s < e; s++) best = max(best, ++cover[s]);
        out.push_back(best);
    }
    return out;
}

JavaScript

var myCalendarThree = function(bookings) {
    var all = [];
    for (var i = 0; i < bookings.length; i++) all.push(bookings[i][0], bookings[i][1]);
    all.sort(function(a, b) { return a - b; });
    var xs = [];
    for (var j = 0; j < all.length; j++) if (j === 0 || all[j] !== all[j - 1]) xs.push(all[j]);
    var find = function(x) {
        var lo = 0, hi = xs.length - 1;
        while (lo < hi) {
            var mid = (lo + hi) >> 1;
            if (xs[mid] < x) lo = mid + 1; else hi = mid;
        }
        return lo;
    };
    var cover = []; // cover[s] counts events over [xs[s], xs[s + 1])
    for (var z = 0; z < xs.length; z++) cover.push(0);
    var best = 0, out = [];
    for (var t = 0; t < bookings.length; t++) {
        var a = find(bookings[t][0]), b = find(bookings[t][1]);
        for (var s = a; s < b; s++) {
            cover[s]++;
            if (cover[s] > best) best = cover[s];
        }
        out.push(best);
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 189 binary search problems · the whole catalogue

Learn the technique: Binary Search · Prefix Sum