Skip to main content
Talentd

My Calendar I - Solution & Explanation

MediumArrayBinary SearchDesignSegment Tree26 min readAsked at: Amazon, Microsoft, Apple +9
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 double booking.

A double booking happens when two events have some non-empty intersection (i.e., some moment is common to both 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 MyCalendar class:

  • MyCalendar() 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 double booking. Otherwise, return false and do not add the event to the calendar.

 

Example 1:

Input
["MyCalendar", "book", "book", "book"]
[[], [10, 20], [15, 25], [20, 30]]
Output
[null, true, false, true]

Explanation
MyCalendar myCalendar = new MyCalendar();
myCalendar.book(10, 20); // return True
myCalendar.book(15, 25); // return False, It can not be booked because time 15 is already booked by another event.
myCalendar.book(20, 30); // return True, The event can be booked, as the first event takes every time less than 20, but not including 20.

 

Constraints:

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

Approach Overview

Problem Overview: Design a calendar system that supports booking events represented as half‑open intervals [start, end). A booking should only succeed if the new event does not overlap with any existing event. The task is to efficiently detect interval conflicts while storing previously accepted bookings.

Approach 1: Brute Force with List (Time: O(n) per booking, Space: O(n))

Store all accepted bookings in a simple list of intervals. When a new booking request arrives, iterate through every stored interval and check for overlap. Two intervals overlap if start < existingEnd and end > existingStart. If any overlap is found, reject the booking; otherwise append the interval to the list. This approach relies only on basic array-style storage and linear scanning. It works well for small input sizes and is easy to implement during an interview, but performance degrades as the number of bookings grows because every operation scans the entire list.

Approach 2: Balanced Tree Using TreeMap (Time: O(log n) per booking, Space: O(n))

A more scalable solution keeps bookings sorted by start time using a balanced search tree such as TreeMap in Java or an ordered structure in C++/Python. Each key represents the start time and the value stores the end time. When inserting a new interval, you only need to check the immediate neighbors in sorted order. Use a floor search to find the previous interval and verify that its end does not exceed the new start. Then use a ceiling search to ensure the next interval does not begin before the new end. Because the structure maintains sorted order internally, each lookup and insertion runs in O(log n). This approach leverages concepts from binary search and ordered set data structures.

Some advanced implementations also model the calendar with a segment tree to support more complex booking queries, but for the constraints of My Calendar I that level of structure is unnecessary.

Recommended for interviews: The balanced tree approach is what most interviewers expect. It shows you understand ordered data structures and how to check only adjacent intervals instead of scanning the entire dataset. Starting with the brute force solution demonstrates correctness and reasoning, while optimizing to O(log n) using a tree structure demonstrates algorithmic maturity.

Approach 1: Approach 1: Brute Force with List

This approach uses a simple list to store existing bookings. For each new booking, we check against all previously booked intervals to ensure there is no overlap. If an overlap is found, the booking is denied; otherwise, it's added to the list. Although straightforward, this approach can be inefficient for many bookings, as each booking incurs a linear scan through the list of existing bookings.

This C program maintains a two-dimensional array 'booked' which stores the start and end of each booking. The 'book' function iterates through existing bookings and checks for overlap. If no overlap is found, it adds the new booking.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(N) for each booking, where N is the number of existing bookings.
Space Complexity: O(N) for storing the bookings.

Try this approach in the editor →

Approach 2: Approach 2: Balanced Tree Using TreeMap

This approach leverages a data structure like a TreeMap (Java) or SortedDict (Python) to efficiently manage and query intervals. These structures allow us to quickly find the nearest existing intervals to check for overlaps, enabling faster insert operations compared to a simple list. By maintaining the intervals in a sorted order, we can reduce the number of overlaps checks necessary for each new booking.

In this Java solution, a TreeMap is used to maintain ordered bookings. 'floorKey' and 'ceilingKey' efficiently find adjacent bookings to check for overlaps with the new booking's start and end times.

Code

JavaPythonC++

Java

Python

C++

Complexity

Time Complexity: O(log N) for each booking due to TreeMap operations.
Space Complexity: O(N).

Try this approach in the editor →

Approach 3: Ordered Set

We can use an ordered set to store the schedule. An ordered set can perform insert, delete, and search operations in O(log n) time. The elements in the ordered set are sorted by the endTime of the schedule in ascending order.

When calling the book(start, end) method, we search for the first schedule in the ordered set with an end time greater than start. If it exists and its start time is less than end, it means there is a double booking, and we return false. Otherwise, we insert end as the key and start as the value into the ordered set and return true.

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

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Brute Force with List

Time Complexity: O(N) for each booking, where N is the number of existing bookings.
Space Complexity: O(N) for storing the bookings.

Approach 2: Balanced Tree Using TreeMap

Time Complexity: O(log N) for each booking due to TreeMap operations.
Space Complexity: O(N).

Ordered Set—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force with ListO(n) per bookingO(n)Simple implementation or small number of bookings
Balanced Tree (TreeMap / Ordered Map)O(log n) per bookingO(n)Large number of bookings where efficient neighbor lookup is required

Video Solution

My Calendar I - Leetcode 729 - Python • NeetCodeIO • 19,483 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is My Calendar I easy or hard?
My Calendar I is classified as Medium difficulty. The brute force solution is straightforward, but identifying the optimal ordered map approach and handling interval edge cases requires a solid understanding of search trees and interval logic.
My Calendar I Python/Java solution
Python solutions typically simulate an ordered structure with sorted lists or libraries like bisect, while Java solutions use TreeMap for efficient floor and ceiling queries. Both implementations achieve O(log n) insertion and overlap checks when using an ordered map.
How to solve My Calendar I in O(log n)?
Store events in a balanced ordered map keyed by start time. For a new interval, find the previous event using a floor lookup and ensure its end time does not exceed the new start. Then check the next event using a ceiling lookup to ensure its start is not before the new end. These operations run in O(log n).
What is the best approach for My Calendar I?
The balanced tree approach using TreeMap or an ordered map is the most efficient and commonly expected solution. By storing events sorted by start time, you only check the immediate previous and next intervals for overlap. Each booking runs in O(log n) time with O(n) space for storing events.
Is My Calendar I asked at Google/Amazon/Meta?
My Calendar I and its follow‑ups appear frequently in system design and data structure interviews at companies like Google, Amazon, and Meta. Interviewers use it to test interval overlap detection and familiarity with ordered data structures.
What data structure is used in My Calendar I?
Common implementations use a list of intervals for the brute force solution or a balanced binary search tree such as TreeMap, ordered map, or ordered set. These structures allow efficient neighbor searches when inserting new intervals.
What is the time complexity of My Calendar I?
The brute force list approach takes O(n) time per booking because it scans every existing event to check for overlap. Using a balanced tree like TreeMap reduces this to O(log n) per booking since it only checks neighboring intervals in the sorted structure.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Determine if Two Events Have Conflict

Next

My Calendar II