My Calendar II

Medium
2058.

My Calendar II

My Calendar II is a medium coding problem on arrays, binary search and prefix sum, asked in Amazon and Google interviews.

You are building a calendar that tolerates double bookings but not triple bookings — some moment of time shared by three events.

An event is the half-open interval [startTime, endTime): it covers every real x with startTime <= x < endTime.

Write the class MyCalendarTwo:

  • MyCalendarTwo() creates an empty calendar.
  • boolean book(int startTime, int endTime) adds the event and returns true if doing so does not create a triple booking; otherwise it leaves the calendar unchanged and returns false.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every void method.

Example 1

Input
["MyCalendarTwo","book","book","book","book","book","book"] [[],[10,20],[50,60],[10,40],[5,15],[5,10],[25,55]]
Output
[null,true,true,true,false,true,true]
Explanation
[10, 40) double-books [10, 20) — allowed. [5, 15) would cover [10, 15) a third time, so it is refused. [5, 10) only touches [10, 40) at its end. [25, 55) double-books [10, 40) and [50, 60) on separate stretches, never three at once.

Example 2

Input
["MyCalendarTwo","book","book","book","book"] [[],[0,10],[0,10],[10,20],[9,11]]
Output
[null,true,true,true,false]
Explanation
Two identical events are fine. [9, 11) would cover [9, 10) a third time, even though the last part, [10, 11), would only be double-booked.

Constraints

  • 0 <= startTime < endTime <= 10^9
  • At most 1000 calls are made to book
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 */
var MyCalendarTwo = function() {
    
};

/**
 * @param {number} startTime
 * @param {number} endTime
 * @return {boolean}
 */
MyCalendarTwo.prototype.book = function(startTime, endTime) {
    
};

Sign in to run your own test cases

Sign in

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

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

My Calendar II is a medium coding problem on arrays, binary search and prefix sum, asked in Amazon and Google interviews.

Problem statement

You are building a calendar that tolerates double bookings but not triple bookings — some moment of time shared by three events.

An event is the half-open interval [startTime, endTime): it covers every real x with startTime <= x < endTime.

Write the class MyCalendarTwo:

  • MyCalendarTwo() creates an empty calendar.
  • boolean book(int startTime, int endTime) adds the event and returns true if doing so does not create a triple booking; otherwise it leaves the calendar unchanged and returns false.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every void method.

Example 1

Input: ["MyCalendarTwo","book","book","book","book","book","book"]
[[],[10,20],[50,60],[10,40],[5,15],[5,10],[25,55]]
Output: [null,true,true,true,false,true,true]
Explanation: [10, 40) double-books [10, 20) — allowed. [5, 15) would cover [10, 15) a third time, so it is refused. [5, 10) only touches [10, 40) at its end. [25, 55) double-books [10, 40) and [50, 60) on separate stretches, never three at once.

Example 2

Input: ["MyCalendarTwo","book","book","book","book"]
[[],[0,10],[0,10],[10,20],[9,11]]
Output: [null,true,true,true,false]
Explanation: Two identical events are fine. [9, 11) would cover [9, 10) a third time, even though the last part, [10, 11), would only be double-booked.

Constraints

  • 0 <= startTime < endTime <= 10^9
  • At most 1000 calls are made to book

Hints for My Calendar II

  1. Hint 1

    A new event creates a triple booking exactly when it overlaps a stretch of time that is already double-booked.

  2. Hint 2

    So keep two lists: every accepted booking, and every stretch that is covered twice (the pairwise overlaps of bookings).

  3. Hint 3

    To book [s, e): refuse if it overlaps any double-booked stretch. Otherwise, add its overlap with each existing booking — [max(s, s2), min(e, e2)) when non-empty — to the double-booked list, then add the event itself.

How to solve My Calendar II

Track the double-booked stretches explicitly. A point becomes triple-booked only if the new event covers a point that two earlier events already cover, i.e. a point inside one of their pairwise overlaps.

Approach

  1. Keep booked (accepted events) and overlaps (stretches covered by two accepted events).
  2. book(s, e): for each [a, b) in overlaps, if s < b and a < e return false.
  3. For each [a, b) in booked, if they overlap, append [max(s, a), min(e, b)) to overlaps.
  4. Append [s, e) to booked and return true.

Why it works

Since no point is ever triple-booked, the points covered twice are exactly the union of the pairwise intersections of accepted events, which is what overlaps holds. A new event creates a triple booking iff it covers such a point — the first check. When it is accepted, the newly double-covered points are exactly its intersections with the earlier events, which the second loop records.

Complexity

  • Time — O(n) per book (n accepted events), O(n²) for n calls
  • Space — O(n)

Pitfalls

  • Check the overlaps list before adding the new event's intersections, or an event is compared with itself.
  • Half-open intervals: events that only touch at an endpoint share no time.
  • A sweep over a sorted map of +1 at starts and -1 at ends (checking that the running count never reaches 3) is the usual alternative, also O(n) per call.

Reference solution

Python

class MyCalendarTwo:

    def __init__(self):
        self.booked = []
        self.overlaps = []  # stretches already covered twice

    def book(self, startTime: int, endTime: int) -> bool:
        for a, b in self.overlaps:
            if startTime < b and a < endTime:
                return False
        for a, b in self.booked:
            if startTime < b and a < endTime:
                self.overlaps.append((max(startTime, a), min(endTime, b)))
        self.booked.append((startTime, endTime))
        return True

Java

class MyCalendarTwo {
    private List<int[]> booked = new ArrayList<>();
    private List<int[]> overlaps = new ArrayList<>(); // stretches already covered twice

    public MyCalendarTwo() {
    }

    public boolean book(int startTime, int endTime) {
        for (int[] o : overlaps) if (startTime < o[1] && o[0] < endTime) return false;
        for (int[] b : booked)
            if (startTime < b[1] && b[0] < endTime)
                overlaps.add(new int[]{Math.max(startTime, b[0]), Math.min(endTime, b[1])});
        booked.add(new int[]{startTime, endTime});
        return true;
    }
}

C++

class MyCalendarTwo {
    vector<pair<int, int>> booked;
    vector<pair<int, int>> overlaps; // stretches already covered twice
public:
    MyCalendarTwo() {}

    bool book(int startTime, int endTime) {
        for (auto& o : overlaps) if (startTime < o.second && o.first < endTime) return false;
        for (auto& b : booked)
            if (startTime < b.second && b.first < endTime)
                overlaps.push_back({max(startTime, b.first), min(endTime, b.second)});
        booked.push_back({startTime, endTime});
        return true;
    }
};

JavaScript

var MyCalendarTwo = function() {
    this.booked = [];
    this.overlaps = []; // stretches already covered twice
};

MyCalendarTwo.prototype.book = function(startTime, endTime) {
    var i;
    for (i = 0; i < this.overlaps.length; i++)
        if (startTime < this.overlaps[i][1] && this.overlaps[i][0] < endTime) return false;
    for (i = 0; i < this.booked.length; i++) {
        var a = this.booked[i][0], b = this.booked[i][1];
        if (startTime < b && a < endTime) this.overlaps.push([Math.max(startTime, a), Math.min(endTime, b)]);
    }
    this.booked.push([startTime, endTime]);
    return true;
};

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

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Binary Search