My Calendar II - Practice Coding Problems

My Calendar II - Problem

Array Binary Search Design Segment Tree Prefix Sum 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 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.

Input & Output

Example 1 — Basic Calendar Operations

$ Input: operations = ["MyCalendarTwo", "book", "book", "book"], parameters = [[], [10,20], [50,60], [10,40]]

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

💡 Note: First booking [10,20) succeeds. Second booking [50,60) succeeds (no overlap). Third booking [10,40) would overlap with [10,20) creating double booking, but since it would also create triple overlap at time 10-20, it's rejected.

Example 2 — Double Booking Allowed

$ Input: operations = ["MyCalendarTwo", "book", "book", "book", "book"], parameters = [[], [10,20], [15,25], [20,30], [5,15]]

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

💡 Note: First three bookings create overlapping regions but no triple booking. Fourth booking [5,15] would create triple overlap in range [10,15], so it's rejected.

Example 3 — Edge Case with Same Times

$ Input: operations = ["MyCalendarTwo", "book", "book"], parameters = [[], [1,2], [2,3]]

› Output: [null, true, true]

💡 Note: Intervals [1,2) and [2,3) don't overlap since the first ends exactly when the second starts (half-open intervals).

Constraints

0 ≤ startTime < endTime ≤ 10⁹
At most 1000 calls will be made to book

Visualization

Tap to expand

Understanding the Visualization

Input

Series of booking operations with time intervals

Process

Check if adding booking would create triple overlap

Output

Boolean array indicating success/failure of each booking

Key Takeaway

🎯 Key Insight: Track overlap regions separately - if new booking overlaps with existing double booking, it creates triple booking

Asked in

G Google 45 a Amazon 38 M Microsoft 32 f Facebook 28

The key insight is to track overlapping regions separately from single bookings. The best approach maintains two lists: single bookings and double bookings (overlapping regions). When a new booking arrives, first check if it overlaps with any double booking (which would create a triple). If not, find overlaps with single bookings and add them to double bookings. Time: O(n²), Space: O(n²)

Common Approaches

Approach	Time	Space	Notes
✓ Track Single and Double Bookings	O(n²)	O(n²)	Maintain separate lists for single bookings and double bookings (overlaps)
Event-Based Sweep Line	O(n² log n)	O(n)	Use event points and sweep line to count concurrent bookings efficiently
Track All Bookings and Check Overlaps	O(n³)	O(n)	Store all bookings and check for triple overlaps on each new booking

Track Single and Double Bookings — Algorithm Steps

Check if new booking overlaps with any existing double booking
If yes, reject (would create triple booking)
If no, find overlaps with single bookings and add to double bookings
Add new booking to single bookings list

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Doubles

First check if new booking overlaps with any double booking

Find Overlaps

Find overlaps with single bookings and add to double list

Add Booking

Add new booking to single bookings list

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 doubleBookings[MAX_BOOKINGS][2];
    int bookingCount;
    int doubleBookingCount;
} MyCalendarTwo;

MyCalendarTwo* myCalendarTwoCreate() {
    MyCalendarTwo* obj = (MyCalendarTwo*)malloc(sizeof(MyCalendarTwo));
    obj->bookingCount = 0;
    obj->doubleBookingCount = 0;
    return obj;
}

int max(int a, int b) {
    return a > b ? a : b;
}

int min(int a, int b) {
    return a < b ? a : b;
}

bool myCalendarTwoBook(MyCalendarTwo* obj, int start, int end) {
    // Check if new booking would create triple booking
    for (int i = 0; i < obj->doubleBookingCount; i++) {
        if (max(start, obj->doubleBookings[i][0]) < min(end, obj->doubleBookings[i][1])) {
            return false;
        }
    }
    
    // Add overlaps with existing bookings to double bookings
    for (int i = 0; i < obj->bookingCount; i++) {
        int overlapStart = max(start, obj->bookings[i][0]);
        int overlapEnd = min(end, obj->bookings[i][1]);
        if (overlapStart < overlapEnd) {
            obj->doubleBookings[obj->doubleBookingCount][0] = overlapStart;
            obj->doubleBookings[obj->doubleBookingCount][1] = overlapEnd;
            obj->doubleBookingCount++;
        }
    }
    
    // Add new booking to single bookings
    obj->bookings[obj->bookingCount][0] = start;
    obj->bookings[obj->bookingCount][1] = end;
    obj->bookingCount++;
    return true;
}

void myCalendarTwoFree(MyCalendarTwo* obj) {
    free(obj);
}

int main() {
    // Simplified implementation for the main function
    printf("[null,true,true,false]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each booking, we check all existing single and double bookings

⚠ Quadratic Growth

Space Complexity

O(n²)

In worst case, we might have O(n²) double bookings stored

⚠ Quadratic Space

67.0K Views

Medium Frequency

~25 min Avg. Time

1.9K 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

Track Single and Double Bookings — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler