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.
- Difficulty: Medium
- Topics: Arrays, Binary Search, Ordered Set, Segment Tree
- Asked at: Amazon, Google, Uber
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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 returnstrueif it does not overlap any event already in the calendar; otherwise it leaves the calendar unchanged and returnsfalse.
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^9At most 1000 calls are made to book
Hints for My Calendar I
Hint 1
Two half-open intervals
[s1, e1)and[s2, e2)overlap exactly whens1 < e2ands2 < e1.Hint 2
Checking every booked event works, but the booked events never overlap each other — keep them sorted by start.
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 afterendTime), and the one before it (it must end bystartTime). 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
- Keep the bookings sorted by start time (an ordered map from start to end, or two parallel sorted arrays).
- Find the first booking whose start is
>= startTime— the successor. If it exists and its start is< endTime, refuse. - Take the booking just before it — the predecessor. If it exists and its end is
> startTime, refuse. - 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 == startof 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 TrueJava
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