My Calendar I

My Calendar I

What is this problem about?

The My Calendar I problem asks you to design a calendar that books events without double-booking. Each event has a start and end time (half-open interval [start, end)). The book(start, end) method should return true if the event can be added without overlapping any existing event, and false otherwise. This My Calendar I coding problem tests interval overlap detection with an ordered data structure.

Why is this asked in interviews?

Uber, Meta, Amazon, TikTok, Google, and Bloomberg ask this because calendar/booking systems are a fundamental real-world design pattern. It tests interval overlap detection and the choice of data structure for efficient querying. The array, design, binary search, ordered set, and segment tree interview pattern is the core.

Algorithmic pattern used

Sorted set (or list) with binary search. Maintain a sorted list of booked intervals. For book(start, end), binary search for the position where the new interval would fit. Check if it overlaps with the previous interval (end > prev.start?) or next interval (start < next.end?). If no overlap, insert the interval. Time: O(log n) for search, O(n) for insert into sorted list; O(log n) with TreeMap in Java.

Example explanation

Book (10, 20): no existing events. Add. Return true. Book (15, 25): check overlap with (10,20). 15 < 20 → overlap! Return false. Book (20, 30): check (10,20). 20 is end of existing, 20 < 20 is false. No overlap. Add. Return true. Book (5, 15): check (10,20). 15 > 10 → overlap! Return false.

Common mistakes candidates make

• Checking start < end of existing AND end > start of existing separately (can simplify to: intervals overlap if NOT (end ≤ existing_start OR start ≥ existing_end)).
• Linear scan for overlap (O(n) per booking) instead of binary search (O(log n)).
• Off-by-one: [start, end) is half-open — start == existing.end is NOT an overlap.
• Not maintaining the sorted order after insertion.

Interview preparation tip

Interval overlap detection is best memorized as: two intervals [a,b) and [c,d) overlap if and only if a < d AND c < b. The negation: they don't overlap if b ≤ c OR d ≤ a. After checking no overlap, insert in sorted order. For Python, use bisect to find the insertion point and check neighbors. This overlap condition is the foundation for My Calendar I, II, and III — master it once and all three become easier.