My Calendar III solution and explanation
Google
9 more videos on this problem
Mastering LeetCode's Hardest Problems in 30 Days or Less! | 'My Calendar III' (Problem 732)HustlerCoder · 27:02 · 8K views
花花酱 LeetCode 732. My Calendar III - 刷题找工作 EP126Hua Hua · 24:44 · 4K views
732. My Calendar IIITech Adora by Nivedita · 15:40 · 3K views
LeetCode 732. My Calendar IIIHappy Coding · 18:08 · 3K views
My Calendar III | Leetcode 732 | Line Sweep Technique Concepts & Questions - 7 | codestorywithMIKcodestorywithMIK · 14:19 · 3K views
732. My Calendar III || DSA || Leetcode Daily Challenge || Code in descriptionLeetcode Daily Challenge · 9:50 · 2K views
Daily Leetcode #920: Oct 07, 2022 - 732. My Calendar IIIProgramming Live with Larry · 21:43 · 871 views
【每日一题】LeetCode 732. My Calendar IIIHuifeng Guan · 15:19 · 585 views
LeetCode 732 My Calendar III Hard Interview Question - Java Solution Using TreeMapAlgorithmicIQ · 19:20 · 498 views
My Calendar III | LeetCode 732 | Asked in Google and Facebook Interview | Explained @LearnOverflowLearn Overflow · 14:10 · 491 views
The 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 integerkrepresenting the largest integer such that there exists ak-booking in the calendar.
Example 1:
Input ["MyCalendarThree", "book", "book", "book", "book", "book", "book"] [[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]] Output [null, 1, 1, 2, 3, 3, 3] Explanation MyCalendarThree myCalendarThree = new MyCalendarThree(); myCalendarThree.book(10, 20); // return 1 myCalendarThree.book(50, 60); // return 1 myCalendarThree.book(10, 40); // return 2 myCalendarThree.book(5, 15); // return 3 myCalendarThree.book(5, 10); // return 3 myCalendarThree.book(25, 55); // return 3
Constraints:
0 <= startTime < endTime <= 109- At most
400calls will be made tobook.
Approach overview
Problem Overview: Design a booking system where each event is an interval [start, end). After every booking, return the maximum number of overlapping events (k-booking) seen so far. The challenge is efficiently tracking overlaps as intervals are inserted one by one.
Approach 1: Sweep Line with Difference Map (O(n) per booking, O(n) space)
This method treats every interval as two events: +1 at start and -1 at end. Store these changes in an ordered structure and perform a prefix scan to compute active overlaps. Each time you book an event, increment the start position and decrement the end position, then iterate through the timeline accumulating the running sum. The maximum prefix value represents the highest number of concurrent events. This is a classic prefix sum style sweep that simulates a timeline of events.
The key insight: overlapping intervals translate into cumulative counts. When multiple events start before previous ones end, the prefix sum naturally grows. This approach is simple to implement and works well for the constraint size of the problem.
Approach 2: Balanced Tree Map (Ordered Map Sweep) (O(n) per booking, O(n) space)
Use a balanced ordered map (such as TreeMap or std::map) to store time points and their delta changes. Insert +1 at the start and -1 at the end of each interval. Because the structure keeps keys sorted, you can iterate through the map to compute the running prefix sum and track the maximum overlap. The ordered structure ensures updates happen in O(log n), while the sweep to compute the maximum takes O(n).
This approach is essentially a structured version of the sweep line technique often used in interval problems and computational geometry. Using an ordered set / map guarantees sorted traversal without extra sorting overhead.
For larger-scale versions of this problem, advanced solutions rely on a dynamic segment tree to track range updates and maximum overlaps in O(log n). That structure is more complex but scales better when the number of bookings becomes very large.
Recommended for interviews: The sweep line with an ordered map is the expected solution. It shows clear understanding of interval overlap problems and prefix accumulation. Explaining the difference-array idea demonstrates strong algorithmic intuition, while mentioning a segment tree extension shows awareness of scalable designs.
Approach 1: Sweep Line Approach
This method uses a line sweep technique, where we process the critical points along the time axis. We treat each event start time as a +1 (which indicates a new event starts), and each end time as a -1 (indicating an event ends).
By maintaining a running sum, we can identify the maximum overlap of events, which gives us the maximum k-booking at any point.
class MyCalendarThree:
def __init__(self):
self.timeline = []
def book(self, start: int, end: int) -> int:
self.timeline.append((start, 1))
self.timeline.append((end, -1))
self.timeline.sort()
max_k, current_k = 0, 0
for time, value in self.timeline:
current_k += value
max_k = max(max_k, current_k)
return max_kimport java.util.*;
class MyCalendarThree {
private List<int[]> timeline;
public MyCalendarThree() {
timeline = new ArrayList<>();
}
public int book(int start, int end) {
timeline.add(new int[]{start, 1});
timeline.add(new int[]{end, -1});
Collections.sort(timeline, (a, b) -> (a[0] == b[0]) ? a[1] - b[1] : a[0] - b[0]);
int maxK = 0, currentK = 0;
for (int[] time : timeline) {
currentK += time[1];
maxK = Math.max(maxK, currentK);
}
return maxK;
}
}class MyCalendarThree {
constructor() {
this.timeline = [];
}
book(start, end) {
this.timeline.push([start, 1]);
this.timeline.push([end, -1]);
this.timeline.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
let maxK = 0, currentK = 0;
for (let i = 0; i < this.timeline.length; i++) {
currentK += this.timeline[i][1];
maxK = Math.max(maxK, currentK);
}
return maxK;
}
}In this Python implementation, we maintain a list of tuples representing time points and their effects (+1 or -1). We sort these time points and iterate over them to calculate the maximum overlapping intervals, thus obtaining the maximum k-booking.
Time Complexity: O(N log N) due to sorting.
Space Complexity: O(N) for storing the timeline of events, where N is the number of events booked.
Approach 2: Balanced Tree Map Approach
A more advanced approach involves using a balanced tree map (or balanced tree data structure) to manage events and efficiently find the maximum overlap.
The map holds start and end times as keys and their occurrences as values. By efficiently summing these up, we can determine the maximum k-booking.
#include <map>
using namespace std;
class MyCalendarThree {
map<int, int> timeline;
public:
MyCalendarThree() {}
int book(int start, int end) {
timeline[start]++;
timeline[end]--;
int maxK = 0, active = 0;
for (auto& [time, count] : timeline) {
active += count;
maxK = max(maxK, active);
}
return maxK;
}
};using System;
using System.Collections.Generic;
public class MyCalendarThree {
private SortedDictionary<int, int> timeline;
public MyCalendarThree() {
timeline = new SortedDictionary<int, int>();
}
public int Book(int start, int end) {
if (!timeline.ContainsKey(start)) timeline[start] = 0;
if (!timeline.ContainsKey(end)) timeline[end] = 0;
timeline[start]++;
timeline[end]--;
int active = 0, maxK = 0;
foreach (var entry in timeline) {
active += entry.Value;
maxK = Math.Max(maxK, active);
}
return maxK;
}
}This C++ implementation employs std::map as a balanced tree to store the impact (+1, -1) at each start and end time. It iterates over the sorted keys to measure the overlapping events count.
Time Complexity: O(N log N) for insertion and traversal.
Space Complexity: O(N) space for the map storing times.
Approach 3: Segment Tree
A segment tree divides the entire interval into multiple non-contiguous subintervals, with the number of subintervals not exceeding log(width). To update the value of an element, we only need to update log(width) intervals, and these intervals are all contained within a larger interval that includes the element. When modifying intervals, we use lazy propagation to ensure efficiency.
- Each node of the segment tree represents an interval.
- The segment tree has a unique root node representing the entire range, such as
[1, N]. - Each leaf node of the segment tree represents a unit interval of length
1,[x, x]. - For each internal node
[l, r], its left child is[l, mid]and its right child is[mid + 1, r], wheremid = \lfloor(l + r) / 2\rfloor(i.e., floor division).
For this problem, the segment tree nodes maintain the following information:
- The maximum number of times the interval has been booked,
v. - Lazy propagation marker,
add.
Since the time range is 10^9, which is very large, we use dynamic node creation.
The time complexity is O(n times log n), and the space complexity is O(n), where n is the number of bookings.
class Node {
left: Node | null = null;
right: Node | null = null;
l: number;
r: number;
mid: number;
v: number = 0;
add: number = 0;
constructor(l: number, r: number) {
this.l = l;
this.r = r;
this.mid = (l + r) >> 1;
}
}
class SegmentTree {
private root: Node = new Node(1, 1e9 + 1);
constructor() {}
modify(l: number, r: number, v: number, node: Node = this.root): void {
if (l > r) {
return;
}
if (node.l >= l && node.r <= r) {
node.v += v;
node.add += v;
return;
}
this.pushdown(node);
if (l <= node.mid) {
this.modify(l, r, v, node.left!);
}
if (r > node.mid) {
this.modify(l, r, v, node.right!);
}
this.pushup(node);
}
query(l: number, r: number, node: Node = this.root): number {
if (l > r) {
return 0;
}
if (node.l >= l && node.r <= r) {
return node.v;
}
this.pushdown(node);
let v = 0;
if (l <= node.mid) {
v = Math.max(v, this.query(l, r, node.left!));
}
if (r > node.mid) {
v = Math.max(v, this.query(l, r, node.right!));
}
return v;
}
private pushup(node: Node): void {
node.v = Math.max(node.left!.v, node.right!.v);
}
private pushdown(node: Node): void {
if (node.left === null) {
node.left = new Node(node.l, node.mid);
}
if (node.right === null) {
node.right = new Node(node.mid + 1, node.r);
}
if (node.add !== 0) {
const left = node.left!;
const right = node.right!;
left.add += node.add;
right.add += node.add;
left.v += node.add;
right.v += node.add;
node.add = 0;
}
}
}
class MyCalendarThree {
private tree: SegmentTree;
constructor() {
this.tree = new SegmentTree();
}
book(start: number, end: number): number {
this.tree.modify(start + 1, end, 1);
return this.tree.query(1, 1e9 + 1);
}
}
/**
* Your MyCalendarThree object will be instantiated and called as such:
* var obj = new MyCalendarThree()
* var param_1 = obj.book(startTime, endTime)
*/type node struct {
left *node
right *node
l, mid, r int
v, add int
}
func newNode(l, r int) *node {
return &node{
l: l,
r: r,
mid: int(uint(l+r) >> 1),
}
}
type segmentTree struct {
root *node
}
func newSegmentTree() *segmentTree {
return &segmentTree{
root: newNode(1, 1e9+1),
}
}
func (t *segmentTree) modify(l, r, v int, n *node) {
if l > r {
return
}
if n.l >= l && n.r <= r {
n.v += v
n.add += v
return
}
t.pushdown(n)
if l <= n.mid {
t.modify(l, r, v, n.left)
}
if r > n.mid {
t.modify(l, r, v, n.right)
}
t.pushup(n)
}
func (t *segmentTree) query(l, r int, n *node) int {
if l > r {
return 0
}
if n.l >= l && n.r <= r {
return n.v
}
t.pushdown(n)
v := 0
if l <= n.mid {
v = max(v, t.query(l, r, n.left))
}
if r > n.mid {
v = max(v, t.query(l, r, n.right))
}
return v
}
func (t *segmentTree) pushup(n *node) {
n.v = max(n.left.v, n.right.v)
}
func (t *segmentTree) pushdown(n *node) {
if n.left == nil {
n.left = newNode(n.l, n.mid)
}
if n.right == nil {
n.right = newNode(n.mid+1, n.r)
}
if n.add != 0 {
n.left.add += n.add
n.right.add += n.add
n.left.v += n.add
n.right.v += n.add
n.add = 0
}
}
type MyCalendarThree struct {
tree *segmentTree
}
func Constructor() MyCalendarThree {
return MyCalendarThree{newSegmentTree()}
}
func (this *MyCalendarThree) Book(start int, end int) int {
this.tree.modify(start+1, end, 1, this.tree.root)
return this.tree.query(1, int(1e9)+1, this.tree.root)
}
/**
* Your MyCalendarThree object will be instantiated and called as such:
* obj := Constructor();
* param_1 := obj.Book(start,end);
*/Complexity comparison
| Approach | Complexity |
|---|---|
| Sweep Line Approach | Time Complexity: O(N log N) due to sorting. |
| Balanced Tree Map Approach | Time Complexity: O(N log N) for insertion and traversal. |
| Segment Tree | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sweep Line with Difference Map | O(n) per booking | O(n) | Best for moderate constraints where simplicity and clarity matter |
| Balanced Tree Map (Ordered Map) | O(n) per booking, O(log n) update | O(n) | Preferred in languages with built-in ordered maps like C++ or C# |
Frequently asked questions
Is My Calendar III easy or hard?
My Calendar III is classified as a Hard problem on LeetCode. The challenge comes from designing a data structure that dynamically tracks overlapping intervals while returning the maximum concurrency after each booking.
My Calendar III Python/Java solution
Python and Java implementations usually rely on a sweep line technique with a sorted dictionary or TreeMap. Each booking updates start and end deltas, and iterating through the map calculates the maximum overlap after every insertion.
How to solve My Calendar III in O(n)?
Maintain a map of time points where starts add +1 and ends add -1. After inserting the changes for a booking, iterate through the sorted keys and maintain a running prefix sum to compute active events. Track the maximum value during the sweep and return it as the current k-booking.
What is the best approach for My Calendar III?
The most common solution uses a sweep line with a difference map. Each booking adds +1 at the start time and -1 at the end time, then a prefix sum scan finds the maximum overlap. This approach runs in O(n) time per booking with O(n) space and is widely used in interview solutions.
Is My Calendar III asked at Google/Amazon/Meta?
My Calendar problems are common interval design questions and have appeared in interviews at companies like Google, Amazon, and Meta. They test understanding of interval overlap, sweep line techniques, and ordered data structures.
What data structure is used in My Calendar III?
Most implementations use an ordered map such as TreeMap or std::map to maintain sorted time points. The algorithm also relies on a prefix sum sweep across these keys to compute active overlaps.
What is the time complexity of My Calendar III?
The typical sweep line implementation takes O(n) time per booking because the algorithm scans all stored time points to compute the running overlap. Updating the ordered map itself costs O(log n), but the prefix traversal dominates the complexity.