Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using array strategy.
You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a triple booking.
A triple booking happens when three events have some non-empty intersection (i.e., some moment is common to all the three events.).
The event can be represented as a pair of integers startTime and endTime that represents a booking on the half-open interval [startTime, endTime), the range of real numbers x such that startTime <= x < endTime.
Implement the MyCalendarTwo class:
MyCalendarTwo() Initializes the calendar object.boolean book(int startTime, int endTime) Returns true if the event can be added to the calendar successfully without causing a triple booking. Otherwise, return false and do not add the event to the calendar.Example 1:
Input ["MyCalendarTwo", "book", "book", "book", "book", "book", "book"] [[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]] Output [null, true, true, true, false, true, true] Explanation MyCalendarTwo myCalendarTwo = new MyCalendarTwo(); myCalendarTwo.book(10, 20); // return True, The event can be booked. myCalendarTwo.book(50, 60); // return True, The event can be booked. myCalendarTwo.book(10, 40); // return True, The event can be double booked. myCalendarTwo.book(5, 15); // return False, The event cannot be booked, because it would result in a triple booking. myCalendarTwo.book(5, 10); // return True, The event can be booked, as it does not use time 10 which is already double booked. myCalendarTwo.book(25, 55); // return True, The event can be booked, as the time in [25, 40) will be double booked with the third event, the time [40, 50) will be single booked, and the time [50, 55) will be double booked with the second event.
Constraints:
0 <= start < end <= 1091000 calls will be made to book.Problem summary: You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a triple booking. A triple booking happens when three events have some non-empty intersection (i.e., some moment is common to all the three events.). The event can be represented as a pair of integers startTime and endTime that represents a booking on the half-open interval [startTime, endTime), the range of real numbers x such that startTime <= x < endTime. Implement the MyCalendarTwo class: MyCalendarTwo() Initializes the calendar object. boolean book(int startTime, int endTime) Returns true if the event can be added to the calendar successfully without causing a triple booking. Otherwise, return false and do not add the event to the calendar.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Binary Search · Design · Segment Tree
["MyCalendarTwo","book","book","book","book","book","book"] [[],[10,20],[50,60],[10,40],[5,15],[5,10],[25,55]]
my-calendar-i)my-calendar-iii)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #731: My Calendar II
class MyCalendarTwo {
private final Map<Integer, Integer> tm = new TreeMap<>();
public MyCalendarTwo() {
}
public boolean book(int startTime, int endTime) {
tm.merge(startTime, 1, Integer::sum);
tm.merge(endTime, -1, Integer::sum);
int s = 0;
for (int v : tm.values()) {
s += v;
if (s > 2) {
tm.merge(startTime, -1, Integer::sum);
tm.merge(endTime, 1, Integer::sum);
return false;
}
}
return true;
}
}
/**
* Your MyCalendarTwo object will be instantiated and called as such:
* MyCalendarTwo obj = new MyCalendarTwo();
* boolean param_1 = obj.book(startTime,endTime);
*/
// Accepted solution for LeetCode #731: My Calendar II
type MyCalendarTwo struct {
rbt *redblacktree.Tree[int, int]
}
func Constructor() MyCalendarTwo {
return MyCalendarTwo{rbt: redblacktree.New[int, int]()}
}
func (this *MyCalendarTwo) Book(startTime int, endTime int) bool {
merge := func(x, v int) {
c, _ := this.rbt.Get(x)
if c+v == 0 {
this.rbt.Remove(x)
} else {
this.rbt.Put(x, c+v)
}
}
merge(startTime, 1)
merge(endTime, -1)
s := 0
for _, v := range this.rbt.Values() {
s += v
if s > 2 {
merge(startTime, -1)
merge(endTime, 1)
return false
}
}
return true
}
/**
* Your MyCalendarTwo object will be instantiated and called as such:
* obj := Constructor();
* param_1 := obj.Book(startTime,endTime);
*/
# Accepted solution for LeetCode #731: My Calendar II
class MyCalendarTwo:
def __init__(self):
self.sd = SortedDict()
def book(self, startTime: int, endTime: int) -> bool:
self.sd[startTime] = self.sd.get(startTime, 0) + 1
self.sd[endTime] = self.sd.get(endTime, 0) - 1
s = 0
for v in self.sd.values():
s += v
if s > 2:
self.sd[startTime] -= 1
self.sd[endTime] += 1
return False
return True
# Your MyCalendarTwo object will be instantiated and called as such:
# obj = MyCalendarTwo()
# param_1 = obj.book(startTime,endTime)
// Accepted solution for LeetCode #731: My Calendar II
use std::collections::BTreeMap;
#[derive(Default)]
struct MyCalendarTwo {
double_booked: Vec<Interval>,
}
impl MyCalendarTwo {
fn new() -> Self {
let double_booked = vec![];
MyCalendarTwo { double_booked }
}
fn book(&mut self, start: i32, end: i32) -> bool {
let mut triple_booked = MyCalendar::new();
for &(a, b) in &self.double_booked {
let a = a.max(start);
let b = b.min(end);
if a < b && !triple_booked.book(a, b) {
return false;
}
}
self.double_booked.push((start, end));
true
}
}
type Interval = (i32, i32);
type Center = i32;
#[derive(Default)]
struct MyCalendar {
btm: BTreeMap<Center, Interval>,
}
impl MyCalendar {
fn new() -> Self {
let btm: BTreeMap<Center, Interval> = BTreeMap::new();
MyCalendar { btm }
}
fn book(&mut self, start: i32, end: i32) -> bool {
let center = start + end;
if let Some((_, &(_, last_end))) = self.btm.range(..=center).next_back() {
if start < last_end {
return false;
}
}
if let Some((_, &(first_start, _))) = self.btm.range(center..).next() {
if first_start < end {
return false;
}
}
self.btm.insert(center, (start, end));
true
}
}
#[test]
fn test() {
let mut obj = MyCalendarTwo::new();
assert_eq!(obj.book(10, 20), true);
assert_eq!(obj.book(50, 60), true);
assert_eq!(obj.book(10, 40), true);
assert_eq!(obj.book(5, 15), false);
assert_eq!(obj.book(5, 10), true);
assert_eq!(obj.book(25, 55), true);
}
// Accepted solution for LeetCode #731: My Calendar II
class MyCalendarTwo {
private tm: Record<number, number> = {};
constructor() {}
book(startTime: number, endTime: number): boolean {
this.tm[startTime] = (this.tm[startTime] ?? 0) + 1;
this.tm[endTime] = (this.tm[endTime] ?? 0) - 1;
let s = 0;
for (const v of Object.values(this.tm)) {
s += v;
if (s > 2) {
if (--this.tm[startTime] === 0) {
delete this.tm[startTime];
}
if (++this.tm[endTime] === 0) {
delete this.tm[endTime];
}
return false;
}
}
return true;
}
}
/**
* Your MyCalendarTwo object will be instantiated and called as such:
* var obj = new MyCalendarTwo()
* var param_1 = obj.book(startTime,endTime)
*/
Use this to step through a reusable interview workflow for this problem.
Check every element from left to right until we find the target or exhaust the array. Each comparison is O(1), and we may visit all n elements, giving O(n). No extra space needed.
Each comparison eliminates half the remaining search space. After k comparisons, the space is n/2ᵏ. We stop when the space is 1, so k = log₂ n. No extra memory needed — just two pointers (lo, hi).
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Setting `lo = mid` or `hi = mid` can stall and create an infinite loop.
Usually fails on: Two-element ranges never converge.
Fix: Use `lo = mid + 1` or `hi = mid - 1` where appropriate.