My Calendar I

Medium
2057.

My Calendar I

My Calendar I is a medium coding problem on arrays, binary search and ordered set, asked in Amazon, Google and Uber interviews.

You are building a calendar. A new event may be added only if it does not cause a double booking — two events sharing some moment of time.

An event is the half-open interval [startTime, endTime): it covers every real x with startTime <= x < endTime, so an event ending at 20 and one starting at 20 do not overlap.

Write the class MyCalendar:

  • MyCalendar() creates an empty calendar.
  • boolean book(int startTime, int endTime) adds the event and returns true if it does not overlap any event already in the calendar; 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
["MyCalendar","book","book","book"] [[],[10,20],[15,25],[20,30]]
Output
[null,true,false,true]
Explanation
[15, 25) overlaps [10, 20) on [15, 20), so it is refused. [20, 30) starts exactly when [10, 20) ends — no overlap.

Example 2

Input
["MyCalendar","book","book","book","book","book"] [[],[47,50],[33,41],[39,45],[33,42],[25,33]]
Output
[null,true,true,false,false,true]
Explanation
[39, 45) overlaps [33, 41) and [33, 42) overlaps it too. [25, 33) ends exactly where [33, 41) begins, so it fits.

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 MyCalendar = function() {
    
};

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

Sign in to run your own test cases

Sign in

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

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

My Calendar I is a medium coding problem on arrays, binary search and ordered set, asked in Amazon, Google and Uber interviews.

Problem statement

You are building a calendar. A new event may be added only if it does not cause a double booking — two events sharing some moment of time.

An event is the half-open interval [startTime, endTime): it covers every real x with startTime <= x < endTime, so an event ending at 20 and one starting at 20 do not overlap.

Write the class MyCalendar:

  • MyCalendar() creates an empty calendar.
  • boolean book(int startTime, int endTime) adds the event and returns true if it does not overlap any event already in the calendar; 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: ["MyCalendar","book","book","book"]
[[],[10,20],[15,25],[20,30]]
Output: [null,true,false,true]
Explanation: [15, 25) overlaps [10, 20) on [15, 20), so it is refused. [20, 30) starts exactly when [10, 20) ends — no overlap.

Example 2

Input: ["MyCalendar","book","book","book","book","book"]
[[],[47,50],[33,41],[39,45],[33,42],[25,33]]
Output: [null,true,true,false,false,true]
Explanation: [39, 45) overlaps [33, 41) and [33, 42) overlaps it too. [25, 33) ends exactly where [33, 41) begins, so it fits.

Constraints

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

Hints for My Calendar I

  1. Hint 1

    Two half-open intervals [s1, e1) and [s2, e2) overlap exactly when s1 < e2 and s2 < e1.

  2. Hint 2

    Checking every booked event works, but the booked events never overlap each other — keep them sorted by start.

  3. Hint 3

    In sorted order, only the two neighbours of the new event's position can conflict: the event starting at or after startTime (it must start at or after endTime), and the one before it (it must end by startTime). Find the position by binary search.

How to solve My Calendar I

The accepted events are pairwise disjoint, so sorted by start they are also sorted by end. A new event can only collide with its immediate neighbours in that order, which a binary search (or an ordered map's floor/ceiling) finds in O(log n).

Approach

  1. Keep the bookings sorted by start time (an ordered map from start to end, or two parallel sorted arrays).
  2. Find the first booking whose start is >= startTime — the successor. If it exists and its start is < endTime, refuse.
  3. Take the booking just before it — the predecessor. If it exists and its end is > startTime, refuse.
  4. Otherwise insert [startTime, endTime) at that position and accept.

Why it works

Every booking after the successor starts even later than the successor, so if the successor does not reach into the new event, none of them does. Every booking before the predecessor ends no later than the predecessor starts (they are disjoint and sorted), so if the predecessor ends by startTime, all earlier ones do too. Hence checking the two neighbours is enough.

Complexity

  • Time — O(log n) per book with a balanced ordered map; O(n) with a sorted array because of the insertion
  • Space — O(n)

Pitfalls

  • The intervals are half-open: end == start of the next event is fine, so compare with strict <.
  • A refused event must not be stored.

Reference solution

Python

from bisect import bisect_left

class MyCalendar:

    def __init__(self):
        self.starts = []  # bookings sorted by start; they never overlap,
        self.ends = []    # so the ends are sorted too

    def book(self, startTime: int, endTime: int) -> bool:
        i = bisect_left(self.starts, startTime)
        if i < len(self.starts) and self.starts[i] < endTime:
            return False
        if i > 0 and self.ends[i - 1] > startTime:
            return False
        self.starts.insert(i, startTime)
        self.ends.insert(i, endTime)
        return True

Java

class MyCalendar {
    private TreeMap<Integer, Integer> cal = new TreeMap<>(); // start -> end

    public MyCalendar() {
    }

    public boolean book(int startTime, int endTime) {
        Map.Entry<Integer, Integer> next = cal.ceilingEntry(startTime);
        if (next != null && next.getKey() < endTime) return false;
        Map.Entry<Integer, Integer> prev = cal.lowerEntry(startTime);
        if (prev != null && prev.getValue() > startTime) return false;
        cal.put(startTime, endTime);
        return true;
    }
}

C++

class MyCalendar {
    map<int, int> cal; // start -> end
public:
    MyCalendar() {}

    bool book(int startTime, int endTime) {
        auto next = cal.lower_bound(startTime);
        if (next != cal.end() && next->first < endTime) return false;
        if (next != cal.begin() && prev(next)->second > startTime) return false;
        cal[startTime] = endTime;
        return true;
    }
};

JavaScript

var MyCalendar = function() {
    this.starts = []; // bookings sorted by start
    this.ends = [];
};

MyCalendar.prototype.book = function(startTime, endTime) {
    var lo = 0, hi = this.starts.length; // first booking starting at or after startTime
    while (lo < hi) {
        var mid = (lo + hi) >> 1;
        if (this.starts[mid] < startTime) lo = mid + 1; else hi = mid;
    }
    if (lo < this.starts.length && this.starts[lo] < endTime) return false;
    if (lo > 0 && this.ends[lo - 1] > startTime) return false;
    this.starts.splice(lo, 0, startTime);
    this.ends.splice(lo, 0, 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