Skip to main content
Talentd

My Calendar II - Solution & Explanation

MediumArrayBinary SearchDesignSegment Tree33 min readAsked at: Amazon, Apple, Google
Practice this problem

Problem Statement

You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a triple booking.

A triple booking happens when three events have some non-empty intersection (i.e., some moment is common to all the three events.).

The event can be represented as a pair of integers startTime and endTime that represents a booking on the half-open interval [startTime, endTime), the range of real numbers x such that startTime <= x < endTime.

Implement the MyCalendarTwo class:

  • MyCalendarTwo() Initializes the calendar object.
  • boolean book(int startTime, int endTime) Returns true if the event can be added to the calendar successfully without causing a triple booking. Otherwise, return false and do not add the event to the calendar.

 

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
MyCalendarTwo myCalendarTwo = new MyCalendarTwo();
myCalendarTwo.book(10, 20); // return True, The event can be booked. 
myCalendarTwo.book(50, 60); // return True, The event can be booked. 
myCalendarTwo.book(10, 40); // return True, The event can be double booked. 
myCalendarTwo.book(5, 15);  // return False, The event cannot be booked, because it would result in a triple booking.
myCalendarTwo.book(5, 10); // return True, The event can be booked, as it does not use time 10 which is already double booked.
myCalendarTwo.book(25, 55); // return True, The event can be booked, as the time in [25, 40) will be double booked with the third event, the time [40, 50) will be single booked, and the time [50, 55) will be double booked with the second event.

 

Constraints:

  • 0 <= start < end <= 109
  • At most 1000 calls will be made to book.

Approach Overview

Problem Overview: You need to design a calendar that supports booking events represented as half-open intervals [start, end). A booking is allowed if it does not create a triple booking. Double bookings are fine, but three overlapping events at the same time must be rejected.

Approach 1: Using Two Lists for Overlapping Intervals (O(n) per booking, O(n) space)

This approach tracks two lists: bookings (all accepted events) and overlaps (intervals that are already double booked). When a new event arrives, first check if it overlaps with anything in overlaps. If it does, the booking would create a triple overlap, so reject it immediately.

If it passes that check, iterate through existing bookings. For every interval that intersects with the new one, compute the intersection and add that range to overlaps. This records the newly created double-booked region. Finally, add the new interval to bookings. The key insight: instead of tracking counts everywhere, explicitly track the ranges where double booking already exists.

This method relies heavily on interval intersection logic and sequential scans using an array. Each booking may compare with all previous events, giving O(n) time per operation and O(n^2) total across all calls in the worst case.

Approach 2: Segment Tree for Interval Overlaps (O(log C) per booking, O(n log C) space)

When the time range becomes large (up to 10^9), scanning intervals repeatedly becomes inefficient. A dynamic segment tree solves this by storing the maximum booking count for each range. Each node represents a segment of time and keeps track of the maximum overlap inside that range.

For every booking request, query the tree to check the maximum overlap in [start, end). If the value is already 2, adding another event would create a triple booking, so reject it. Otherwise, update the range by incrementing its count. Lazy propagation allows efficient range updates without expanding the entire tree.

This method treats the problem as a range frequency update problem similar to sweep-line or prefix sum techniques, but implemented with a tree so queries stay logarithmic. Each booking runs in O(log C) time where C is the coordinate range.

Recommended for interviews: The two-list interval method is the most commonly expected answer. It is short, easy to reason about, and demonstrates clear understanding of interval overlaps. The segment tree approach shows deeper knowledge of advanced data structures and range queries, which can impress in system-heavy or follow-up interview questions.

Approach 1: Approach 1: Using Two Lists for Overlapping Intervals

In this approach, we maintain two separate lists: `single_booked` for bookings that have been added without conflicts, and `double_booked` for intervals where two events overlap. To add a new booking:

  1. First, check if it causes a triple booking by comparing it with the existing `double_booked` intervals. If any interval in `double_booked` overlaps with the new booking, it indicates a triple booking.
  2. If no triple booking is detected, proceed to update the lists:
  3. Check the new booking against `single_booked`. If there's an overlap with an interval in `single_booked`, this represents a double booking, and the overlapping part should be added to `double_booked`.
  4. Finally, add the current booking to `single_booked`.

The C solution defines two lists to store the single_booked and double_booked intervals. The `book` function checks for triple bookings by testing overlaps with double_booked, then adds any necessary doubles before adding the event to the single_booked list.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(N^2) because for each booking, we might need to check with all existing ones.
Space Complexity: O(N) to store all bookings.

Try this approach in the editor →

Approach 2: Approach 2: Segment Tree for Interval Overlaps

In this approach, we use a segment tree to efficiently keep track of overlapping intervals. By maintaining a segment tree, we can:

  1. Efficiently query the total number of active bookings over any particular interval to avoid triple bookings.
  2. Allow immediate updates whenever a new booking starts or ends, thus adjusting the tree in place.

This approach is optimal for datasets with large integer boundaries due to the logarithmic nature of segment trees for both update and query operations.

The C++ solution uses a `map` to simulate a segment tree on a line sweep basis. As intervals are booked or end, we increment or decrement from the timeline, respectively. The `book` method tracks active bookings to ensure it never surpasses two overlapping intervals.

Code

C++JavaPythonC#JavaScript

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(N log N) due to map operations.
Space Complexity: O(N) for map storage.

Try this approach in the editor →

Approach 3: Difference Array

We can use the concept of a difference array to record the booking status at each time point. Then, we traverse all the time points and count the booking status at the current time point. If the number of bookings exceeds 2, we return false. Otherwise, we return true.

The time complexity is O(n^2), and the space complexity is O(n), where n is the number of bookings.

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Approach 4: Segment Tree

A segment tree divides the entire interval into multiple non-contiguous subintervals, with the number of subintervals not exceeding log(width). To update the value of an element, only log(width) intervals need to be updated, and these intervals are all contained within a larger interval that includes the element. When modifying intervals, a lazy mark is used to ensure efficiency.

  • Each node of the segment tree represents an interval;
  • The segment tree has a unique root node representing the entire statistical range, such as [1, N];
  • Each leaf node of the segment tree represents a unit interval of length 1, [x, x];
  • For each internal node [l, r], its left child is [l, mid] and its right child is [mid + 1, r], where mid = \lfloor(l + r) / 2\rfloor (i.e., floor division).

For this problem, the segment tree nodes maintain the following information:

  1. The maximum number of bookings within the interval v
  2. Lazy mark add

Since the time range is 10^9, which is very large, we use dynamic node creation.

The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the number of bookings.

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Using Two Lists for Overlapping Intervals

Time Complexity: O(N^2) because for each booking, we might need to check with all existing ones.
Space Complexity: O(N) to store all bookings.

Approach 2: Segment Tree for Interval Overlaps

Time Complexity: O(N log N) due to map operations.
Space Complexity: O(N) for map storage.

Difference Array—
Segment Tree—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Two Lists for Overlapping IntervalsO(n) per booking, O(n^2) totalO(n)Best for interviews and moderate constraints; simple logic using interval comparisons
Segment Tree with Lazy PropagationO(log C) per bookingO(n log C)When time coordinates are large and frequent range queries or updates are required

Video Solution

My Calendar II - Leetcode 731 - Python • NeetCodeIO • 13,849 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is My Calendar II easy or hard?
My Calendar II is rated Medium because it requires careful handling of interval overlaps. The core trick is realizing that tracking double-booked regions prevents triple bookings. Once that insight is clear, the implementation becomes straightforward.
My Calendar II Python/Java solution
In Python or Java, the simplest implementation keeps two lists: bookings and overlaps. For each new interval, check conflicts with overlaps first, then compute intersections with existing bookings before inserting the event. The logic is identical across Python, Java, C++, C#, and JavaScript.
How to solve My Calendar II in O(n)?
Each booking can be handled in O(n) time by storing two arrays: booked intervals and double-booked intervals. First check the new event against all double-booked ranges to prevent triple overlaps. Then compute intersections with existing bookings and store those intersections as new double-booked ranges.
What is the best approach for My Calendar II?
The most practical approach uses two lists: one for all bookings and another for already double-booked intervals. Before adding a new event, check whether it overlaps with any interval in the double-booked list. This ensures triple bookings never occur. The method runs in O(n) time per booking and is the solution most interviewers expect.
Is My Calendar II asked at Google/Amazon/Meta?
My Calendar II is a common design-style interval problem seen in interviews at companies like Google, Amazon, and Meta. It tests understanding of interval overlaps, event scheduling logic, and sometimes advanced structures like segment trees or sweep-line techniques.
What data structure is used in My Calendar II?
Typical solutions use arrays or lists to store intervals and track overlaps. Advanced implementations may use a segment tree, ordered map, or sweep-line technique with prefix sums to maintain the number of active bookings across ranges.
What is the time complexity of My Calendar II?
The common two-list interval approach runs in O(n) time for each booking because the new event may be compared with every previous booking. Across n bookings the worst-case complexity becomes O(n^2). Using a segment tree reduces each operation to O(log C), where C is the time coordinate range.

Ready to solve this problem?

Practice My Calendar II with our built-in code editor and test cases.

Practice on FleetCode
Previous

My Calendar I

Next

My Calendar III