My Calendar I - Practice Coding Problems

My Calendar I - Problem

Array Binary Search Design Segment Tree Ordered Set Medium

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.

Input & Output

Example 1 — Basic Calendar Operations

$ Input: commands = ["MyCalendar", "book", "book", "book"], parameters = [[], [10, 20], [15, 25], [20, 30]]

› Output: [null, true, false, true]

💡 Note: MyCalendar() initializes calendar. book(10,20) returns true (first booking). book(15,25) returns false (overlaps with [10,20)). book(20,30) returns true (no overlap since [10,20) ends at 20).

Example 2 — Adjacent Bookings

$ Input: commands = ["MyCalendar", "book", "book"], parameters = [[], [10, 20], [20, 30]]

› Output: [null, true, true]

💡 Note: book(10,20) succeeds. book(20,30) succeeds because intervals [10,20) and [20,30) don't overlap (20 is not included in first interval).

Example 3 — Multiple Overlaps

$ Input: commands = ["MyCalendar", "book", "book", "book", "book"], parameters = [[], [5, 10], [25, 30], [15, 20], [12, 18]]

› Output: [null, true, true, true, false]

💡 Note: First three bookings succeed. book(12,18) fails because it overlaps with [15,20): max(12,15) < min(18,20) → 15 < 18 is true.

Constraints

0 ≤ start < end ≤ 10⁹
At most 1000 calls will be made to book

Visualization

Tap to expand

Understanding the Visualization

Input

Booking requests with start and end times

Process

Check for overlaps with existing bookings

Output

Return true/false for each booking attempt

Key Takeaway

🎯 Key Insight: Two intervals overlap if their intersection is non-empty - use max(start1,start2) < min(end1,end2) to detect overlaps efficiently

Asked in

G Google 15 M Microsoft 12 A Amazon 10 🍎 Apple 8

The key insight is that two intervals [a,b) and [c,d) overlap if max(a,c) < min(b,d). The linear search approach checks all existing bookings for overlap in O(n) time. For better performance, use binary search on sorted bookings to find insertion position quickly. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Linear Search	O(n)	O(n)	Store all bookings in a list and check each one for overlap
Sorted List with Binary Search	O(n)	O(n)	Keep bookings sorted and use binary search to find potential overlaps

Linear Search — Algorithm Steps

Store all bookings in a list
For each new booking, check against all existing bookings
If no overlap found, add the booking and return true

Visualization

Tap to expand

Step-by-Step Walkthrough

Existing Bookings

List of current bookings

Check Overlap

Compare new booking with each existing one

Add or Reject

Add if no overlap, reject otherwise

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_BOOKINGS 1000

typedef struct {
    int bookings[MAX_BOOKINGS][2];
    int size;
} MyCalendar;

MyCalendar* myCalendarCreate() {
    MyCalendar* obj = (MyCalendar*)malloc(sizeof(MyCalendar));
    obj->size = 0;
    return obj;
}

bool myCalendarBook(MyCalendar* obj, int start, int end) {
    for (int i = 0; i < obj->size; i++) {
        int maxStart = (start > obj->bookings[i][0]) ? start : obj->bookings[i][0];
        int minEnd = (end < obj->bookings[i][1]) ? end : obj->bookings[i][1];
        if (maxStart < minEnd) {
            return false;
        }
    }
    obj->bookings[obj->size][0] = start;
    obj->bookings[obj->size][1] = end;
    obj->size++;
    return true;
}

int main() {
    // Simple implementation for this approach
    MyCalendar* calendar = myCalendarCreate();
    
    // Example: book(10,20), book(15,25), book(20,30)
    printf("[null,%s,%s,%s]\n",
        myCalendarBook(calendar, 10, 20) ? "true" : "false",
        myCalendarBook(calendar, 15, 25) ? "true" : "false",
        myCalendarBook(calendar, 20, 30) ? "true" : "false");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each book operation checks all existing bookings

✓ Linear Growth

Space Complexity

O(n)

Store all bookings in a list

⚡ Linearithmic Space

98.5K Views

Medium Frequency

~15 min Avg. Time

2.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Linear Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler