308. My Calendar I
🔗 LeetCode Problem: 729. My Calendar I
📊 Difficulty: Medium
🏷️ Topics: Design, Segment Tree, Binary Search, Ordered Set
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 start and end that represents a booking on the half-open interval [start, end), the range of real numbers x such that start <= x < end.
Implement the MyCalendar class:
- MyCalendar() Initializes the calendar object.
- boolean book(int start, int end) 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.
Example 1:
Input:
["MyCalendar", "book", "book", "book"]
[[], [10, 20], [15, 25], [20, 30]]
Output:
[null, true, false, true]
Explanation:
MyCalendar myCalendar = new MyCalendar();
myCalendar.book(10, 20); // return True
myCalendar.book(15, 25); // return False (conflicts with [10,20))
myCalendar.book(20, 30); // return True
Constraints:
- 0 <= start < end <= 10^9
- At most 1000 calls will be made to book.
🌳 Visual Understanding - The Calendar Problem
The Problem We're Solving:
Think of it like booking time slots in a calendar:
Existing bookings: [10, 20), [20, 30)
Timeline:
0 5 10 15 20 25 30 35
|----BOOKED----|----BOOKED----|
Try to book [15, 25):
0 5 10 15 20 25 30 35
|----BOOKED----|----BOOKED----|
|--NEW?--|
Overlaps with [10,20)! ✗
Return FALSE
Try to book [30, 40):
0 5 10 15 20 25 30 35 40
|----BOOKED----|----BOOKED----|
|--NEW?--|
No overlap! ✓
Add to calendar
Return TRUE
Understanding Half-Open Intervals:
[start, end) means:
- Includes start
- EXCLUDES end
- "start <= x < end"
Examples:
[10, 20) includes 10, 11, ..., 19 (NOT 20!)
[20, 30) includes 20, 21, ..., 29 (NOT 30!)
Important: [10,20) and [20,30) DON'T overlap!
First ends at 20 (excluded)
Second starts at 20 (included)
They TOUCH but don't overlap!
This is different from closed intervals [a, b]!
Key Observations:
1. Need to check if new booking overlaps with ANY existing booking
Even ONE overlap means we can't book
2. Two intervals [a,b) and [c,d) overlap if:
a < d AND c < b
(They DON'T overlap if a >= d OR c >= b)
3. Need EFFICIENT checking
Brute force: Check all existing bookings O(n)
Better: Use sorted structure with binary search O(log n)
4. This is a DESIGN problem
Need to choose right data structure!
🧠 Discovering the Solution - Intuitive Approach
Let's Think Through This:
Question 1: When do two intervals overlap?
Two half-open intervals [a,b) and [c,d) overlap if:
They share at least one point
Visual approach - they DON'T overlap if:
Case 1: First ends before second starts
[a,b) [c,d)
|---| |---|
a b < c d
b <= c (first ends before/at second start)
Case 2: Second ends before first starts
[c,d) [a,b)
|---| |---|
c d < a b
d <= a (second ends before/at first start)
So they OVERLAP if NEITHER case is true:
NOT (b <= c OR d <= a)
= a < d AND c < b
This is THE overlap formula! 🔑
Examples:
[10,20) and [15,25): 10 < 25 AND 15 < 20 → OVERLAP ✓
[10,20) and [20,30): 10 < 30 AND 20 < 20? NO → No overlap ✓
[10,20) and [5,12): 10 < 12 AND 5 < 20 → OVERLAP ✓
Question 2: How to check overlap efficiently?
Approach 1: Brute Force
For each new booking:
Check against ALL existing bookings
Time: O(n) per book call
Works but not optimal for many bookings!
Approach 2: Sorted Structure + Binary Search
Keep bookings sorted by start time
For new booking [start, end):
Find where it would go in sorted list
Only check neighbors!
Time: O(log n) to find position, O(1) to check neighbors
But inserting takes O(n) (shifting array)
Approach 3: TreeMap/TreeSet
Java TreeMap: Sorted map with O(log n) operations
For new booking [start, end):
Use floorEntry (booking before) and ceilingEntry (booking after)
Only check these two!
Time: O(log n) for all operations
This is OPTIMAL! 🎯
Question 3: Why only check neighbors in sorted list?
Key insight: If bookings are sorted by start time,
a new booking can only overlap with its NEIGHBORS!
Proof:
Bookings sorted: [..., A, (new position), B, ...]
A comes before new:
A.start <= new.start
If A doesn't overlap new:
A.end <= new.start
Then ALL bookings before A also don't overlap!
(Their ends are even earlier)
B comes after new:
new.start < B.start
If B doesn't overlap new:
new.end <= B.start
Then ALL bookings after B also don't overlap!
(Their starts are even later)
So we ONLY need to check immediate neighbors! ✨
🟢 Approach 1: Brute Force - Check All Bookings
💡 Intuition
Simple approach:
Store all bookings in a list
For each new booking:
Check if it overlaps with ANY existing booking
If no overlap: add it
If overlap: reject it
Easy to understand, works for small number of bookings
📝 Implementation
import java.util.*;
class MyCalendar {
private List<int[]> bookings;
public MyCalendar() {
bookings = new ArrayList<>();
}
public boolean book(int start, int end) {
// Check against all existing bookings
for (int[] booking : bookings) {
int existingStart = booking[0];
int existingEnd = booking[1];
// Check if [start, end) overlaps with [existingStart, existingEnd)
if (start < existingEnd && existingStart < end) {
// Overlap detected!
return false;
}
}
// No overlap found, add the booking
bookings.add(new int[]{start, end});
return true;
}
}
📊 Complexity Analysis
Time Complexity:
book(): O(n)
Check all existing bookings: O(n)
With k calls to book:
Total: O(1 + 2 + 3 + ... + k) = O(k²)
Space Complexity: O(n)
Store all n bookings
🟢 Approach 2: TreeMap with Neighbor Checking (Optimal)
💡 Intuition
Use TreeMap to keep bookings sorted by start time:
Key: start time
Value: end time
For new booking [start, end):
1. Find previous booking (largest start < new start)
2. Find next booking (smallest start > new start)
3. Only check these two for overlap!
4. If no overlap: add to TreeMap
Why this works:
Sorted structure + only checking neighbors
All operations: O(log n)
🎨 Building the Solution
TreeMap API we need:
- floorEntry(key): Entry with largest key <= given key
- ceilingEntry(key): Entry with smallest key >= given key
- put(key, value): Add new entry
For new booking [start, end):
1. Check previous booking (ends before or overlaps?)
prev = floorEntry(start)
if prev.value > start: overlap!
2. Check next booking (starts after or overlaps?)
next = ceilingEntry(start)
if next.key < end: overlap!
3. If both checks pass: add booking
📝 Implementation
import java.util.*;
class MyCalendar {
private TreeMap<Integer, Integer> calendar;
public MyCalendar() {
calendar = new TreeMap<>();
}
public boolean book(int start, int end) {
// Find previous booking (largest start <= new start)
Map.Entry<Integer, Integer> prev = calendar.floorEntry(start);
// Find next booking (smallest start >= new start)
Map.Entry<Integer, Integer> next = calendar.ceilingEntry(start);
// Check if previous booking overlaps
if (prev != null && prev.getValue() > start) {
// Previous booking ends after new booking starts
// Overlap detected!
return false;
}
// Check if next booking overlaps
if (next != null && next.getKey() < end) {
// Next booking starts before new booking ends
// Overlap detected!
return false;
}
// No overlap found, add the booking
calendar.put(start, end);
return true;
}
}
🔍 Complete Dry Run
Input: book(10,20), book(15,25), book(20,30)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Call 1: book(10, 20)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
calendar = {} (empty)
Check previous:
prev = floorEntry(10) = null
No previous booking, no conflict
Check next:
next = ceilingEntry(10) = null
No next booking, no conflict
Add booking:
calendar = {10: 20}
Return: TRUE ✓
Timeline:
10 15 20 25 30
|--------|
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Call 2: book(15, 25)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
calendar = {10: 20}
Check previous:
prev = floorEntry(15) = (10, 20)
prev.getValue() = 20
20 > 15? YES
Previous booking ends (20) after new booking starts (15)
OVERLAP DETECTED! ✗
Return: FALSE ✓
Timeline:
10 15 20 25 30
| -------- |
| -------- |✗ CONFLICT!
calendar remains: {10: 20}
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Call 3: book(20, 30)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
calendar = {10: 20}
Check previous:
prev = floorEntry(20) = (10, 20)
prev.getValue() = 20
20 > 20? NO
Previous booking ends (20) at exactly where new starts (20)
No overlap! (half-open intervals)
Check next:
next = ceilingEntry(20) = null
No next booking, no conflict
Add booking:
calendar = {10: 20, 20: 30}
Return: TRUE ✓
Timeline:
10 15 20 25 30
|--------|--------| ✓ NO CONFLICT!
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
FINAL STATE
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
calendar = {10: 20, 20: 30}
Results: [true, false, true] ✓
Complex Example
book(5,10) → TRUE calendar = {5:10}
book(10,15) → TRUE calendar = {5:10, 10:15} (touching at 10)
book(8,12) → FALSE (overlaps both 5:10 and 10:15)
book(15,20) → TRUE calendar = {5:10, 10:15, 15:20}
book(9,11) → FALSE (overlaps 5:10 and 10:15)
Timeline after successful bookings:
5 10 15 20
|----|----|----|
📊 Complexity Analysis
Time Complexity:
book(): O(log n)
floorEntry(): O(log n)
ceilingEntry(): O(log n)
put(): O(log n)
With k calls:
Total: O(k log k)
Much better than brute force O(k²)! 🎯
Space Complexity: O(n)
Store n bookings in TreeMap
🎯 Key Insights Summary
The Three Critical Points:
1. Overlap Condition for Half-Open Intervals
[a,b) and [c,d) overlap if:
a < d AND c < b
NOT if:
a >= d OR c >= b
Half-open means:
[10,20) and [20,30) DON'T overlap
20 is excluded from first, included in second
They just TOUCH
This is THE formula to remember! 🔑
2. Only Check Neighbors in Sorted List
If bookings sorted by start time:
New booking can only overlap with neighbors!
Why?
Booking before: if it doesn't overlap, none before it will
Booking after: if it doesn't overlap, none after it will
This reduces O(n) checks to just 2 checks! ✓
3. TreeMap for Efficient Sorted Storage
TreeMap provides:
- Sorted order by key
- floorEntry(): previous booking
- ceilingEntry(): next booking
- All operations: O(log n)
Perfect data structure for this problem! 🎯
💡 Why This Approach Works - Deep Intuition
The Neighbor Property:
Question: Why only check neighbors?
Answer: Think about sorted intervals:
[..., A, B, (new), C, D, ...]
If new doesn't overlap with B (previous):
new.start >= B.end
Since A ends even earlier (A.end <= B.end):
new.start >= A.end too!
So A won't overlap either!
Neither will anything before A!
If new doesn't overlap with C (next):
new.end <= C.start
Since D starts even later (D.start >= C.start):
new.end <= D.start too!
So D won't overlap either!
Neither will anything after D!
Therefore: Only neighbors matter! ✨
⚠️ Common Mistakes
// Mistake 1: Wrong overlap condition
if (start <= existingEnd && existingStart <= end) { // ❌
// ✓ CORRECT: For half-open intervals
if (start < existingEnd && existingStart < end) {
// Mistake 2: Not handling null from floorEntry/ceilingEntry
if (prev.getValue() > start) { // ❌ NullPointerException if prev is null!
// ✓ CORRECT:
if (prev != null && prev.getValue() > start) {
// Mistake 3: Checking wrong condition for next
if (next != null && next.getKey() <= end) { // ❌ Should be <
// ✓ CORRECT: For half-open intervals
if (next != null && next.getKey() < end) {
// Mistake 4: Adding booking before checking all conflicts
calendar.put(start, end);
if (hasConflict) return false; // ❌ Already added!
// ✓ CORRECT: Check first, then add
if (hasConflict) return false;
calendar.put(start, end);
// Mistake 5: Using ceiling(start) instead of ceilingEntry(start)
Map.Entry<Integer, Integer> next = calendar.ceiling(start); // ❌ Wrong method!
// ✓ CORRECT:
Map.Entry<Integer, Integer> next = calendar.ceilingEntry(start);
📝 Quick Revision Notes
🎯 Core Concept
Problem: Book events without double-booking
Key Insight: Use TreeMap + check only neighbors!
Algorithm: 1. Find previous booking (floorEntry) 2. Check if previous overlaps (prev.end > new.start) 3. Find next booking (ceilingEntry) 4. Check if next overlaps (next.start < new.end) 5. If no overlap: add booking
Why It Works: Sorted bookings + neighbor property!
⚡ Quick Implementation
import java.util.Map.Entry;
import java.util.TreeMap;
class MyCalendar {
TreeMap<Integer, Integer> map;
public MyCalendar() {
map = new TreeMap<>();
}
public boolean book(int start, int end) {
// step 2: get the interval just before the
// incoming input start interval (prev)
// If that interval's end overlap, return false.
// map: {10:20}
// incoming: (15,25)
// floorEntry: 10 => its value 20 > 15 => overlap
Entry<Integer, Integer> prev = map.floorEntry(start);
if (prev != null && prev.getValue() > start) {
return false;
}
// step 3: get the interval just after the
// incoming input start interval (next)
// Rest is same
Entry<Integer, Integer> next = map.ceilingEntry(start);
// incoming: [15,25]
// map's ceil entry: {20,30} => next
// 25 should be < 20
if (next != null && end > next.getKey()) {
return false;
}
// step 1: put start and end times in map.
map.put(start, end);
return true;
}
}
public class Solution {
public static void main(String[] args) {
MyCalendar mc = new MyCalendar();
// System.out.println(mc.book(10, 20) == true);
// System.out.println(mc.book(15, 25) == false);
// System.out.println(mc.book(20, 30) == true);
System.out.println(mc.book(47, 50));
System.out.println(mc.book(33, 41));
}
}
🔑 Key Points
✓ Half-open intervals: [a,b) excludes b
✓ Overlap: a < d AND c < b
✓ TreeMap keeps sorted order
✓ Only check previous and next booking
✓ floorEntry: previous, ceilingEntry: next
✓ Time: O(log n), Space: O(n)
🎪 Memory Aid
"Half-open touch is fine!"
"Previous and next, check in line!"
"TreeMap sorted, neighbors define!"
"Log time booking, design divine!" ✨
🎉 Congratulations!
You've mastered My Calendar I!
What You Learned:
✅ Half-open intervals - [a,b) semantics
✅ Overlap detection - Efficient formula
✅ Sorted data structure - TreeMap usage
✅ Neighbor optimization - Check only adjacent
✅ Design problem - Choosing right structure
The Beautiful Insight:
Calendar Booking → Sorted Intervals + Neighbor Check
The core insight:
"Don't check all existing bookings!"
"Sort them, only check neighbors"
Why neighbors?
If previous doesn't overlap → none before do
If next doesn't overlap → none after do
This reduces O(n) to O(log n)!
This pattern appears in:
- Interval scheduling
- Resource allocation
- Time slot booking
- Range overlap detection
Master this = Handle interval conflicts efficiently! ✨
Interview Mastery:
When asked about My Calendar:
1. Understand: "Book events without double-booking"
2. Clarify: "Half-open intervals [a,b) - exclude endpoint"
3. Brute force: "Check all existing bookings - O(n) per book"
4. Key insight: "Keep bookings sorted by start time.
Only need to check neighbors!"
5. Why neighbors: "If previous doesn't overlap, none before it will.
If next doesn't overlap, none after it will."
6. Data structure: "TreeMap perfect - sorted + O(log n) ops"
7. Algorithm: "Use floorEntry for previous, ceilingEntry for next.
Check both for overlap."
8. Overlap check: "For half-open: a < d AND c < b"
9. Complexity: "O(log n) per book, O(n) space"
Shows design and optimization skills! 💯
You've mastered an important design problem! The TreeMap + neighbor checking pattern is powerful for many interval problems! 🚀✨🎯