How to Solve My Calendar I

This problem requires implementing a calendar that prevents double bookings by checking event overlaps before insertion. Using a sorted list of existing events, you can apply binary search to quickly find the correct insertion point. Each booking attempt returns true if the event can be added without conflict and false otherwise, enforcing the half-open interval rule.

Problem Statement

You are tasked with designing a personal calendar system that allows adding new events while preventing overlapping times. Each event is defined by a start and end time, and it can only be added if it does not intersect any existing events. An event is represented by a half-open interval [start, end), meaning the start time is inclusive and the end time is exclusive.

A double booking occurs when two events share any common time. Your system should efficiently handle a sequence of booking requests and return whether each booking is successful. Constraints include 0 <= start < end <= 10^9 and at most 1000 booking calls, emphasizing the need for efficient insertion and conflict checking.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

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.

Solution Approach

Store events in a sorted list

Maintain a list of already booked intervals sorted by start time. This ordering allows using binary search to find where a new event could fit while preserving the sorted property, directly supporting fast conflict checks.

Binary search for insertion

For each booking request, perform a binary search to locate the position where the new interval would be inserted. Check only the neighboring intervals for overlap, leveraging the sorted property to reduce the number of comparisons compared to a linear scan.

Check for conflicts

After finding the insertion point, verify that the new interval does not overlap with the previous or next intervals. If no conflict exists, insert the event and return true; otherwise, reject the booking and return false. This ensures no double booking occurs, enforcing the half-open interval rule.

Complexity Analysis

Time complexity is O(N log N) due to binary search for each booking in a list of N events. Space complexity is O(N) to store all booked intervals.

What Interviewers Usually Probe

• Consider the performance of repeated booking checks and how sorting or search impacts efficiency.
• Mention that using a sorted list plus binary search avoids checking all events linearly.
• Demonstrate understanding of half-open interval semantics to avoid off-by-one overlap errors.

Common Pitfalls or Variants

Common pitfalls

• Failing to handle the half-open interval correctly, allowing end times to conflict with start times.
• Performing linear scans for each booking, leading to O(N^2) behavior with many events.
• Neglecting to check both neighboring intervals when inserting a new event in the sorted list.

Follow-up variants

• Extending to My Calendar II or III, which allow one or multiple overlaps and require interval counting.
• Using a balanced binary search tree or segment tree instead of a list for faster dynamic insertions.
• Supporting queries for free time slots or event counts within a range instead of single bookings.

How GhostInterview Helps

• Provides a guided implementation pattern for storing intervals and applying binary search efficiently.
• Highlights edge cases such as boundary overlaps and the half-open interval requirement.
• Optimizes your code to avoid unnecessary linear scans, focusing on practical performance for up to 1000 bookings.

Topic Pages

• Array
• Binary Search
• Design
• Segment Tree
• Ordered Set

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What is the main strategy to prevent double bookings in My Calendar I?

Use a sorted list of existing intervals and binary search to find the insertion point, then check adjacent intervals for conflicts.

How do half-open intervals affect booking logic?

Half-open intervals [start, end) mean the start time is included but the end is excluded, so two events touching at boundaries do not overlap.

Can we optimize beyond linear scans for this problem?

Yes, binary search over the sorted event list reduces the number of comparisons from O(N) to O(log N) per booking.

What are common mistakes when implementing this calendar?

Ignoring boundary conditions, failing to check both neighbors for overlap, or using inefficient scans for each insertion.

Why is this problem categorized under binary search over valid answer space?

Because each booking requires locating the correct interval position in a sorted list, binary search efficiently determines whether insertion is valid.