#729
My Calendar I
Medium Ordered map (floor / ceiling)
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Book half-open time intervals [start, end). Reject a booking if it overlaps any existing one.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: accept a booking only if it doesn't overlap an existing one.
Why this works: in a sorted map, only the booking just before and the one just after the new start can clash.
Example: book [10,20] ✓, [15,25] → previous ends at 20 > 15 → ✗, [20,30] ✓
✦Hints open one at a time
Keep bookings sorted by start in a TreeMap.
Only the closest booking before and after the new start can overlap it.
↗Approach
floorEntry(start) must end at or before start; ceilingKey(start) must be at or after end. If both hold, insert.
</>Solution (Java)
import java.util.*;
class MyCalendar {
private final TreeMap<Integer, Integer> bookings = new TreeMap<>(); // start -> end
public boolean book(int start, int end) {
Map.Entry<Integer, Integer> before = bookings.floorEntry(start);
Integer after = bookings.ceilingKey(start);
if (before != null && before.getValue() > start) return false; // previous one runs into us
if (after != null && after < end) return false; // next one starts too early
bookings.put(start, end);
return true;
}
}!Common mistake
Scanning every booking — O(n) per call, O(n²) overall. (A segment tree is the heavier tool for the harder versions.)
Complexity
- Time: O(log n) per booking.
- Space: O(n).
Topic: Segment Tree, Fenwick & Sparse Table
🎬 Episodes 98–100: video coming soon