My Calendar III - Practice Coding Problems

My Calendar III - Problem

A k-booking happens when k events have some non-empty intersection (i.e., there is some time that is common to all k events.)

You are given some events [startTime, endTime), after each given event, return an integer k representing the maximum k-booking between all the previous events.

Implement the MyCalendarThree class:

MyCalendarThree() Initializes the object.
int book(int startTime, int endTime) Returns an integer k representing the largest integer such that there exists a k-booking in the calendar.

Input & Output

Example 1 — Basic Booking Sequence

$ Input: operations = ["MyCalendarThree","book","book","book"], values = [[],[10,20],[15,25],[20,30]]

› Output: [1,2,2]

💡 Note: First book(10,20) returns 1. Second book(15,25) overlaps with first, max k-booking is 2. Third book(20,30) doesn't increase maximum overlap, still 2.

Example 2 — Multiple Overlaps

$ Input: operations = ["MyCalendarThree","book","book","book","book"], values = [[],[10,40],[20,30],[25,35],[5,15]]

› Output: [1,2,3,3]

💡 Note: Progressive overlap: first booking alone (1), second overlaps with first (2), third overlaps with both first and second at time 25-30 (3), fourth doesn't increase maximum.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Sequence of booking operations with [start, end) intervals

Process

Track maximum number of overlapping intervals at any time

Output

Return k-booking count after each operation

Key Takeaway

🎯 Key Insight: Use difference array to efficiently track booking count changes at start/end times

Asked in

G Google 25 a Amazon 18 M Microsoft 15

The optimal approach uses a difference array technique with a map. We increment the count at start time and decrement at end time, then calculate the prefix sum to find maximum overlapping bookings. Time: O(n²), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Difference Array with Map	O(n²)	O(n)	Use difference array technique with map to efficiently track booking counts
Brute Force with List Storage	O(n²)	O(n)	Store all intervals and count overlaps for each booking

Difference Array with Map — Algorithm Steps

Use map to store difference array
Increment at start, decrement at end
Calculate prefix sum to find maximum overlap

Visualization

Tap to expand

Step-by-Step Walkthrough

Update Deltas

Increment at start, decrement at end

Calculate Prefix Sum

Sum deltas to get active bookings

Track Maximum

Return highest active count

Code -

solution.c — C

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

#define MAX_EVENTS 1000

typedef struct {
    int time;
    int delta;
} TimePoint;

typedef struct {
    TimePoint points[MAX_EVENTS * 2];
    int count;
} MyCalendarThree;

MyCalendarThree* myCalendarThreeCreate() {
    MyCalendarThree* obj = (MyCalendarThree*)malloc(sizeof(MyCalendarThree));
    obj->count = 0;
    return obj;
}

int compare(const void* a, const void* b) {
    TimePoint* pa = (TimePoint*)a;
    TimePoint* pb = (TimePoint*)b;
    return pa->time - pb->time;
}

int myCalendarThreeBook(MyCalendarThree* obj, int start, int end) {
    // Find or create start time
    int startIdx = -1, endIdx = -1;
    for (int i = 0; i < obj->count; i++) {
        if (obj->points[i].time == start) {
            startIdx = i;
            break;
        }
    }
    if (startIdx == -1) {
        obj->points[obj->count].time = start;
        obj->points[obj->count].delta = 0;
        startIdx = obj->count++;
    }
    obj->points[startIdx].delta++;
    
    // Find or create end time
    for (int i = 0; i < obj->count; i++) {
        if (obj->points[i].time == end) {
            endIdx = i;
            break;
        }
    }
    if (endIdx == -1) {
        obj->points[obj->count].time = end;
        obj->points[obj->count].delta = 0;
        endIdx = obj->count++;
    }
    obj->points[endIdx].delta--;
    
    qsort(obj->points, obj->count, sizeof(TimePoint), compare);
    
    int active = 0, maxK = 0;
    for (int i = 0; i < obj->count; i++) {
        active += obj->points[i].delta;
        if (active > maxK) maxK = active;
    }
    
    return maxK;
}

int main() {
    printf("[1,2,3]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each booking, we iterate through all stored time points to calculate prefix sum

⚠ Quadratic Growth

Space Complexity

O(n)

Map stores at most 2n entries (start and end times)

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~25 min Avg. Time

856 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

Difference Array with Map — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler