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.
- Difficulty: Medium
- Topics: Arrays, Binary Search, Prefix Sum, Ordered Set, Segment Tree
- Asked at: Amazon, Google
- 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 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 returnstrueif doing so does not create a triple booking; 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: ["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^9At most 1000 calls are made to book
Hints for My Calendar II
Hint 1
A new event creates a triple booking exactly when it overlaps a stretch of time that is already double-booked.
Hint 2
So keep two lists: every accepted booking, and every stretch that is covered twice (the pairwise overlaps of bookings).
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
- Keep
booked(accepted events) andoverlaps(stretches covered by two accepted events). book(s, e): for each[a, b)inoverlaps, ifs < banda < ereturnfalse.- For each
[a, b)inbooked, if they overlap, append[max(s, a), min(e, b))tooverlaps. - Append
[s, e)tobookedand returntrue.
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
+1at starts and-1at 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 TrueJava
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