What is the time complexity of My Calendar I?

The optimal solution has a time complexity of O(n).

What data structures are used to solve My Calendar I?

This problem uses Array, Binary Search, Design, Segment Tree, Ordered Set. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving My Calendar I?

Insight 1: The calendar needs to maintain the events in sorted order by start time to efficiently check for overlaps. Insight 2: Binary search is an efficient way to find the correct insertion point for a new event while maintaining the sorted order.

Which companies ask LeetCode 729. My Calendar I in interviews?

This problem is frequently asked at Flexport.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

My Calendar I - LeetCode 729 Solution

Q: How to solve My Calendar I?

The solution uses a sorted list (or vector in C++) to store the events in the calendar. When a new event is to be booked, a binary search is performed to find the correct position to insert the new event, maintaining sorted order. Before inserting, the algorithm checks for overlap between the new event and the existing events directly before and after the insertion point. If no overlap is found, the new event is inserted into the calendar, and `true` is returned. Otherwise, `false` is returned without modifying the calendar.

My Calendar I - Complete Solution Guide

My Calendar I is LeetCode problem 729, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

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: M

Detailed Explanation

The problem is to design a calendar that prevents double bookings. A double booking occurs when two events have overlapping time intervals. The `MyCalendar` class should have a `book` method that takes a start time and an end time as input and returns `true` if the event can be added to the calendar without causing a double booking. Otherwise, it returns `false` and does not add the event. The time intervals are half-open intervals, meaning they include the start time but exclude the end time (e.g., [10, 20) includes 10 up to, but not including, 20). The constraints are 0 <= start < end <= 10^9 and at most 1000 calls to book.

Solution Approach

The solution uses a sorted list (or vector in C++) to store the events in the calendar. When a new event is to be booked, a binary search is performed to find the correct position to insert the new event, maintaining sorted order. Before inserting, the algorithm checks for overlap between the new event and the existing events directly before and after the insertion point. If no overlap is found, the new event is inserted into the calendar, and `true` is returned. Otherwise, `false` is returned without modifying the calendar.

Step-by-Step Algorithm

Step 1: Initialize an empty list (or vector) called `calendar` to store the events. Each event will be represented as a pair of integers: [startTime, endTime].
Step 2: When the `book(startTime, endTime)` method is called, use binary search (or `bisect_left` in Python, `lower_bound` in C++) to find the index `idx` where the new event should be inserted to maintain the sorted order of start times.
Step 3: Check for overlap with the event immediately before the insertion point (if it exists). If `idx > 0`, check if `calendar[idx - 1][1] > startTime`. If true, there's an overlap, so return `false`.
Step 4: Check for overlap with the event immediately after the insertion point (if it exists). If `idx < len(calendar)`, check if `calendar[idx][0] < endTime`. If true, there's an overlap, so return `false`.
Step 5: If no overlaps are found in steps 3 and 4, insert the new event [startTime, endTime] at index `idx` in the `calendar`.
Step 6: Return `true` to indicate that the event was successfully booked.

Key Insights

Insight 1: The calendar needs to maintain the events in sorted order by start time to efficiently check for overlaps.
Insight 2: Binary search is an efficient way to find the correct insertion point for a new event while maintaining the sorted order.
Insight 3: To check for overlaps, it's sufficient to compare the new event with its immediate neighbors (the event before and the event after) in the sorted calendar.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

Topics

This problem involves: Array, Binary Search, Design, Segment Tree, Ordered Set.

Companies

Asked at: Flexport.

My Calendar I | LeetCode 729

Medium

Array Binary Search Design Segment Tree Ordered Set

Time: O(n)Space: O(n)

Solution Code

Available in:

import java.util.ArrayList;
import java.util.List;

class MyCalendar {

    private List<int[]> calendar;

    public MyCalendar() {
        calendar = new ArrayList<>();
    }

    public boolean book(int startTime, int endTime) {
        // bisect_left finds the insertion point for startTime to maintain sorted order.
        // Python's list comparison works element by element, so it correctly sorts by start time.
        int idx = binarySearch(startTime);

        // Check for overlap with the previous event.
        // If idx > 0, there's an event at calendar[idx-1].
        // The previous event is [prev_start, prev_end]. We know prev_start <= startTime.
        // An overlap occurs if the new event starts before the previous one ends.
        // i.e., startTime < prev_end.
        if (idx > 0 && calendar.get(idx - 1)[1] > startTime) {
            return false;
        }

        // Check for overlap with the next event.
        // If idx < len(self.calendar), there's an event at calendar[idx].
        // The next event is [next_start, next_end]. We know startTime <= next_start.
        // An overlap occurs if the new event ends after the next one begins.
        // i.e., endTime > next_start.
        if (idx < calendar.size() && calendar.get(idx)[0] < endTime) {
            return false;
        }

        // If no overlaps are found, insert the event at the correct position.
        calendar.add(idx, new int[]{startTime, endTime});
        return true;
    }

    private int binarySearch(int startTime) {
        int low = 0;
        int high = calendar.size();

        while (low < high) {
            int mid = low + (high - low) / 2;
            if (calendar.get(mid)[0] < startTime) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }
}

/**
 * Your MyCalendar object will be instantiated and called as such:
 * MyCalendar obj = new MyCalendar();
 * boolean param_1 = obj.book(startTime,endTime);
 */

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 729: My Calendar I - Detailed explanation and solution approaches.

Topics

Array Binary Search Design Segment Tree Ordered Set

Companies

Flexport

Stats

Difficulty:Medium

Languages:4

Companies:1

Problem #:729

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

6 steps

1
Step 1: Initialize an empty list (or vector) called `calendar` to store the events. Each event will be represented as a pair of integers: [startTime, endTime].
2
Step 2: When the `book(startTime, endTime)` method is called, use binary search (or `bisect_left` in Python, `lower_bound` in C++) to find the index `idx` where the new event should be inserted to maintain the sorted order of start times.
3
Step 3: Check for overlap with the event immediately before the insertion point (if it exists). If `idx > 0`, check if `calendar[idx - 1][1] > startTime`. If true, there's an overlap, so return `false`.
4
Step 4: Check for overlap with the event immediately after the insertion point (if it exists). If `idx < len(calendar)`, check if `calendar[idx][0] < endTime`. If true, there's an overlap, so return `false`.
5
Step 5: If no overlaps are found in steps 3 and 4, insert the new event [startTime, endTime] at index `idx` in the `calendar`.
6
Step 6: Return `true` to indicate that the event was successfully booked.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The binary search contributes O(log n) for locating the insertion point. However, the insertion of an element at a specific index `idx` into an `ArrayList` (Java) or `std::vector` (C++) or Python List requires shifting elements after `idx`, resulting in a worst-case time complexity of O(n). The space complexity is O(n) because the `calendar` stores all events. Thus, both time and space grow linearly with the number of events.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Segment Tree

Use a segment tree to represent the calendar. Each node in the segment tree represents a time interval, and the value of the node indicates whether the interval is booked or not. This allows for efficient overlap checking.

Time: O(log n) for booking an event.Space: O(n) for storing the segment tree.

Trade-offs: Segment trees offer better time complexity for the `book` operation (O(log n)) but are more complex to implement than the sorted list approach. Use segment trees when there are a very large number of booking operations, and performance is critical.

Ordered Set (TreeSet in Java, set in C++)

Store events as intervals in an ordered set. Use methods to find lower bound and upper bound events to check for overlaps. Using an ordered set will maintain the sorted order of events automatically, and finding the insertion point will be logarithmic.

Time: O(log n) for booking an eventSpace: O(n)

Trade-offs: This approach provides O(log n) time complexity for booking. It utilizes data structures that maintain order automatically. Implementation is slightly more complex, but may be more efficient than the insertion method used in the primary solution.

✨

Key Insights

1Insight 1: The calendar needs to maintain the events in sorted order by start time to efficiently check for overlaps.
2Insight 2: Binary search is an efficient way to find the correct insertion point for a new event while maintaining the sorted order.
3Insight 3: To check for overlaps, it's sufficient to compare the new event with its immediate neighbors (the event before and the event after) in the sorted calendar.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Binary Search

Halving the search space each step. Like finding a word in a dictionary!

Edge Cases

Edge case 1: Booking the first event. The checks for the previous and next events will be skipped because the calendar is empty, and the event will be inserted correctly.
Edge case 2: Booking an event that is adjacent to an existing event. For example, if the calendar contains [10, 20), booking [20, 30) should be allowed because the end time of the first event is equal to the start time of the second event (no overlap). The solution correctly handles this since the comparisons are `startTime < prev_end` and `endTime > next_start`.
Edge case 3: Booking an event that is completely contained within the range of another event is handled correctly, as the overlap checks will detect the collision.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Incorrectly checking for overlap by using incorrect comparison operators (e.g., using <= instead of <). It's important to understand that the intervals are half-open.

✗Common mistake 2: Forgetting to handle the edge cases where the new event is the first or last event in the calendar, which may cause out-of-bounds errors when accessing neighboring events.

✗Common mistake 3: Failing to resize the calendar array in C when it's full, leading to memory access errors.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Scheduling meetings in a calendar application, where it's important to avoid double bookings.

🏦Real-world scenario 2: Booking resources (e.g., rooms, equipment) in a company or university, ensuring that the same resource is not booked for overlapping time slots by different users.

🎮Real-world scenario 3: Flight or hotel booking systems. Ensuring that flights and hotel rooms are not overbooked.

📱Real-world scenario 4: Resource allocation in cloud computing environments.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Medium problems are the bread and butter of technical interviews. Practice explaining your approach before coding.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: June 10, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJun 6

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92May 30

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterMay 23

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

Can binary search be applied to non-sorted arrays?

Binary search requires a monotonic property, not necessarily sorted data. It can be applied to any search space where you can determine if the answer is in the left or right half. Examples include searching rotated arrays or finding minimum in optimization problems.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "My Calendar I"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether binary search techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?