Facebook Pixel

729. My Calendar I

MediumDesignSegment TreeArrayBinary SearchOrdered Set
Leetcode Link

Problem Description

You need to implement a calendar system that can add events without causing double bookings. A double booking occurs when two events have some overlap in time (they share at least one moment in common).

Each event is represented by two integers: startTime and endTime, defining a time interval [startTime, endTime). This is a half-open interval, meaning it includes startTime but excludes endTime.

You need to implement the MyCalendar class with the following methods:

  • MyCalendar(): Initializes an empty calendar object
  • book(int startTime, int endTime): Attempts to add a new event to the calendar
    • Returns true if the event can be added without causing a double booking (and adds it)
    • Returns false if adding the event would cause a double booking (and doesn't add it)

The solution uses a SortedDict data structure where:

  • Keys are the endTime values of events
  • Values are the corresponding startTime values

When booking a new event [start, end):

  1. The code finds the position where this event would fit based on its start time using bisect_right(start)
  2. It checks if there's an existing event at that position whose startTime (stored as value) is less than the new event's end time
  3. If such an overlap exists, it returns false
  4. Otherwise, it adds the new event (with end as key and start as value) and returns true

This approach cleverly stores events as {end: start} pairs in the sorted dictionary, allowing efficient checking for overlaps in O(log n) time.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

To detect double bookings, we need to check if a new event overlaps with any existing events. Two events [start1, end1) and [start2, end2) overlap if and only if start1 < end2 AND start2 < end1.

The key insight is that we need an efficient way to find potential overlapping events. If we store events in a sorted manner, we can quickly identify the events that might overlap with a new booking.

Why store events as {endTime: startTime} pairs in a sorted dictionary? This clever design choice comes from observing that:

  1. When we want to book a new event [start, end), the events that could potentially overlap are those whose endTime > start (if an event ends before or at our start time, there's no overlap).

  2. By using bisect_right(start), we find the first event in our sorted dictionary whose endTime > start. This is our only candidate for overlap.

  3. Among all events with endTime > start, we only need to check the one with the smallest endTime (which bisect_right gives us). Why? Because if this event doesn't overlap, no other event will overlap either.

  4. For this candidate event, we check if its startTime < end. If true, there's an overlap. If false, we're safe to add the new event.

The beauty of this approach is that we reduce the overlap checking problem from comparing against all existing events O(n) to just checking one strategically chosen event O(log n). By maintaining events sorted by their end times and storing start times as values, we can quickly identify and check the only event that matters for overlap detection.

Learn more about Segment Tree and Binary Search patterns.

Solution Approach

The solution uses a SortedDict (ordered set/map) to maintain all booked events. The key insight is storing events as {endTime: startTime} pairs, which allows us to efficiently check for overlaps.

Data Structure Choice:

  • We use a SortedDict where keys are automatically kept in sorted order
  • Keys represent endTime of events
  • Values represent startTime of events
  • This provides O(log n) time complexity for insertion and search operations

Implementation Steps:

  1. Initialization (__init__):

    • Create an empty SortedDict to store all booked events

  2. Booking Logic (book method):

    When trying to book a new event [start, end):

    a. Find potential overlap candidate:

    • Use bisect_right(start) to find the index of the first event whose endTime > start
    • This returns the position where an event with key start would be inserted to maintain sorted order

    b. Check for overlap:

    • If idx < len(self.sd) (meaning we found an event with endTime > start)
    • AND if self.sd.values()[idx] < end (meaning that event's startTime < end)
    • Then we have an overlap: both conditions for intersection are met
    • Return False without adding the event

    c. Add the event if no overlap:

    • If no overlap is detected, insert the new event: self.sd[end] = start
    • Return True to indicate successful booking

Why this works:

  • For any new event [start, end), only events with endTime > start can possibly overlap
  • Among these, we only need to check the one with the smallest endTime (which bisect_right finds)
  • If this closest event doesn't overlap, no other event will overlap either
  • The overlap condition is satisfied when the found event's startTime < end

Time Complexity:

  • book: O(log n) for both the search (bisect_right) and insertion operations
  • Space Complexity: O(n) where n is the number of successfully booked events

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through booking several events to see how the solution works:

Initial State: Calendar is empty, SortedDict = {}

Book Event 1: [10, 20)

  • Call bisect_right(10) on empty dict → returns index 0
  • Since index 0 < length(0), no existing events to check
  • Add event: SortedDict = {20: 10}
  • Return true

Book Event 2: [25, 35)

  • Call bisect_right(25) on keys [20] → returns index 1
  • Since index 1 is not < length(1), no event with endTime > 25 exists
  • Add event: SortedDict = {20: 10, 35: 25}
  • Return true

Book Event 3: [15, 30) (This will overlap!)

  • Call bisect_right(15) on keys [20, 35] → returns index 1
    • This finds the first event whose endTime > 15, which is the event with key 35
  • Check overlap: index 1 < length(2), so check the event at index 1
    • Event at index 1: endTime = 35, startTime = 25
    • Is startTime(25) < new event's end(30)? Yes!
    • This means [25, 35) overlaps with [15, 30)
  • Return false without adding

Book Event 4: [5, 10)

  • Call bisect_right(5) on keys [20, 35] → returns index 0
    • This finds the first event whose endTime > 5, which is the event with key 20
  • Check overlap: index 0 < length(2), so check the event at index 0
    • Event at index 0: endTime = 20, startTime = 10
    • Is startTime(10) < new event's end(10)? No! (10 is not < 10)
    • No overlap detected
  • Add event: SortedDict = {10: 5, 20: 10, 35: 25}
  • Return true

Book Event 5: [8, 12) (This will overlap!)

  • Call bisect_right(8) on keys [10, 20, 35] → returns index 1
    • This finds the first event whose endTime > 8, which is the event with key 20
  • Check overlap: index 1 < length(3), so check the event at index 1
    • Event at index 1: endTime = 20, startTime = 10
    • Is startTime(10) < new event's end(12)? Yes!
    • This means [10, 20) overlaps with [8, 12)
  • Return false without adding

Final State: SortedDict = {10: 5, 20: 10, 35: 25} representing events [5,10), [10,20), and [25,35)

The key insight illustrated here: by storing events as {endTime: startTime} and using bisect_right on the start time of a new event, we directly find the one event that could potentially overlap, making the check extremely efficient.

Solution Implementation

1from sortedcontainers import SortedDict
2
3
4class MyCalendar:
5    def __init__(self):
6        # Initialize a sorted dictionary to store intervals
7        # Key: end time, Value: start time
8        self.sorted_intervals = SortedDict()
9
10    def book(self, start: int, end: int) -> bool:
11        """
12        Attempt to book a time interval [start, end).
13      
14        Args:
15            start: Start time of the interval (inclusive)
16            end: End time of the interval (exclusive)
17          
18        Returns:
19            True if booking is successful (no overlap), False otherwise
20        """
21        # Find the first interval whose end time is greater than the start time
22        # This finds potential overlapping intervals
23        index = self.sorted_intervals.bisect_right(start)
24      
25        # Check if there's an overlap with the found interval
26        # If the found interval's start time is less than our end time,
27        # then there's an overlap
28        if index < len(self.sorted_intervals) and list(self.sorted_intervals.values())[index] < end:
29            return False
30      
31        # No overlap found, add the new interval to the calendar
32        # Store as (end_time -> start_time) for efficient overlap checking
33        self.sorted_intervals[end] = start
34        return True
35
36
37# Your MyCalendar object will be instantiated and called as such:
38# obj = MyCalendar()
39# param_1 = obj.book(start, end)
40
1class MyCalendar {
2    // TreeMap to store booked intervals: key = endTime, value = startTime
3    private final TreeMap<Integer, Integer> bookedIntervals = new TreeMap<>();
4
5    public MyCalendar() {
6        // Constructor - no initialization needed as TreeMap is already instantiated
7    }
8
9    public boolean book(int startTime, int endTime) {
10        // Find the first interval whose endTime is greater than the new interval's startTime
11        // We use startTime + 1 to exclude intervals that end exactly at our start time (no overlap)
12        Map.Entry<Integer, Integer> potentialOverlap = bookedIntervals.ceilingEntry(startTime + 1);
13      
14        // Check if there's an overlap:
15        // If an interval exists and its startTime is less than our endTime,
16        // then there's an overlap and we cannot book this interval
17        if (potentialOverlap != null && potentialOverlap.getValue() < endTime) {
18            return false;
19        }
20      
21        // No overlap found, so we can book this interval
22        // Store the interval as (endTime -> startTime) in the TreeMap
23        bookedIntervals.put(endTime, startTime);
24        return true;
25    }
26}
27
28/**
29 * Your MyCalendar object will be instantiated and called as such:
30 * MyCalendar obj = new MyCalendar();
31 * boolean param_1 = obj.book(startTime,endTime);
32 */
33
1class MyCalendar {
2public:
3    MyCalendar() {
4        // Constructor - initializes an empty calendar
5    }
6
7    bool book(int startTime, int endTime) {
8        // Find the first booked interval whose end time is greater than the new interval's start time
9        // We use startTime + 1 to exclude intervals that end exactly when this one starts (no overlap)
10        auto nextInterval = bookedIntervals.lower_bound(startTime + 1);
11      
12        // Check if there's an overlap with the found interval
13        // If such an interval exists AND its start time is before our end time, there's an overlap
14        if (nextInterval != bookedIntervals.end() && nextInterval->second < endTime) {
15            return false;  // Booking failed due to overlap
16        }
17      
18        // No overlap found, add the new interval to our calendar
19        // Store as: key = end time, value = start time
20        bookedIntervals[endTime] = startTime;
21        return true;  // Booking successful
22    }
23
24private:
25    // Map to store booked intervals
26    // Key: end time of interval, Value: start time of interval
27    // This structure allows efficient checking of overlaps using lower_bound
28    map<int, int> bookedIntervals;
29};
30
31/**
32 * Your MyCalendar object will be instantiated and called as such:
33 * MyCalendar* obj = new MyCalendar();
34 * bool param_1 = obj->book(startTime,endTime);
35 */
36
1// Type definition for comparison function
2type CompareFunction<T> = (lhs: T, rhs: T) => number;
3
4// Red-Black Tree Node class
5class RedBlackTreeNode<T = number> {
6    data: T;
7    count: number;
8    left: RedBlackTreeNode<T> | null;
9    right: RedBlackTreeNode<T> | null;
10    parent: RedBlackTreeNode<T> | null;
11    color: number; // 0 = RED, 1 = BLACK
12
13    constructor(data: T) {
14        this.data = data;
15        this.left = null;
16        this.right = null;
17        this.parent = null;
18        this.color = 0; // New nodes are RED by default
19        this.count = 1; // For handling duplicate values
20    }
21
22    // Get the sibling node of current node
23    sibling(): RedBlackTreeNode<T> | null {
24        if (!this.parent) return null;
25        return this.isOnLeft() ? this.parent.right : this.parent.left;
26    }
27
28    // Check if current node is left child of its parent
29    isOnLeft(): boolean {
30        return this === this.parent!.left;
31    }
32
33    // Check if current node has at least one red child
34    hasRedChild(): boolean {
35        return (
36            Boolean(this.left && this.left.color === 0) ||
37            Boolean(this.right && this.right.color === 0)
38        );
39    }
40}
41
42// Red-Black Tree implementation
43class RedBlackTree<T> {
44    root: RedBlackTreeNode<T> | null;
45    lessThan: (left: T, right: T) => boolean;
46
47    constructor(compareFunc: CompareFunction<T> = (left: T, right: T) => (left < right ? -1 : left > right ? 1 : 0)) {
48        this.root = null;
49        this.lessThan = (left: T, right: T) => compareFunc(left, right) < 0;
50    }
51
52    // Left rotation around given node
53    rotateLeft(pivotNode: RedBlackTreeNode<T>): void {
54        const rightChild = pivotNode.right!;
55        pivotNode.right = rightChild.left;
56
57        if (pivotNode.right) {
58            pivotNode.right.parent = pivotNode;
59        }
60        rightChild.parent = pivotNode.parent;
61
62        if (!pivotNode.parent) {
63            this.root = rightChild;
64        } else if (pivotNode === pivotNode.parent.left) {
65            pivotNode.parent.left = rightChild;
66        } else {
67            pivotNode.parent.right = rightChild;
68        }
69
70        rightChild.left = pivotNode;
71        pivotNode.parent = rightChild;
72    }
73
74    // Right rotation around given node
75    rotateRight(pivotNode: RedBlackTreeNode<T>): void {
76        const leftChild = pivotNode.left!;
77        pivotNode.left = leftChild.right;
78
79        if (pivotNode.left) {
80            pivotNode.left.parent = pivotNode;
81        }
82        leftChild.parent = pivotNode.parent;
83
84        if (!pivotNode.parent) {
85            this.root = leftChild;
86        } else if (pivotNode === pivotNode.parent.left) {
87            pivotNode.parent.left = leftChild;
88        } else {
89            pivotNode.parent.right = leftChild;
90        }
91
92        leftChild.right = pivotNode;
93        pivotNode.parent = leftChild;
94    }
95
96    // Swap colors of two nodes
97    swapColor(node1: RedBlackTreeNode<T>, node2: RedBlackTreeNode<T>): void {
98        const tempColor = node1.color;
99        node1.color = node2.color;
100        node2.color = tempColor;
101    }
102
103    // Swap data of two nodes
104    swapData(node1: RedBlackTreeNode<T>, node2: RedBlackTreeNode<T>): void {
105        const tempData = node1.data;
106        node1.data = node2.data;
107        node2.data = tempData;
108    }
109
110    // Fix Red-Black Tree properties after insertion
111    fixAfterInsert(currentNode: RedBlackTreeNode<T>): void {
112        let parentNode = null;
113        let grandParentNode = null;
114
115        // Fix violations while node is not root, not black, and parent is red
116        while (currentNode !== this.root && currentNode.color !== 1 && currentNode.parent?.color === 0) {
117            parentNode = currentNode.parent;
118            grandParentNode = currentNode.parent.parent;
119
120            // Case A: Parent is left child of grandparent
121            if (parentNode === grandParentNode?.left) {
122                const uncleNode = grandParentNode.right;
123
124                // Case 1: Uncle is red - only recoloring needed
125                if (uncleNode && uncleNode.color === 0) {
126                    grandParentNode.color = 0;
127                    parentNode.color = 1;
128                    uncleNode.color = 1;
129                    currentNode = grandParentNode;
130                } else {
131                    // Case 2: Current is right child - left rotation required
132                    if (currentNode === parentNode.right) {
133                        this.rotateLeft(parentNode);
134                        currentNode = parentNode;
135                        parentNode = currentNode.parent;
136                    }
137
138                    // Case 3: Current is left child - right rotation required
139                    this.rotateRight(grandParentNode);
140                    this.swapColor(parentNode!, grandParentNode);
141                    currentNode = parentNode!;
142                }
143            } else {
144                // Case B: Parent is right child of grandparent
145                const uncleNode = grandParentNode!.left;
146
147                // Case 1: Uncle is red - only recoloring needed
148                if (uncleNode != null && uncleNode.color === 0) {
149                    grandParentNode!.color = 0;
150                    parentNode.color = 1;
151                    uncleNode.color = 1;
152                    currentNode = grandParentNode!;
153                } else {
154                    // Case 2: Current is left child - right rotation required
155                    if (currentNode === parentNode.left) {
156                        this.rotateRight(parentNode);
157                        currentNode = parentNode;
158                        parentNode = currentNode.parent;
159                    }
160
161                    // Case 3: Current is right child - left rotation required
162                    this.rotateLeft(grandParentNode!);
163                    this.swapColor(parentNode!, grandParentNode!);
164                    currentNode = parentNode!;
165                }
166            }
167        }
168        // Root must always be black
169        this.root!.color = 1;
170    }
171
172    // Delete single occurrence of value
173    delete(value: T): boolean {
174        const nodeToDelete = this.find(value);
175        if (!nodeToDelete) return false;
176        nodeToDelete.count--;
177        if (!nodeToDelete.count) {
178            this.deleteNode(nodeToDelete);
179        }
180        return true;
181    }
182
183    // Delete all occurrences of value
184    deleteAll(value: T): boolean {
185        const nodeToDelete = this.find(value);
186        if (!nodeToDelete) return false;
187        this.deleteNode(nodeToDelete);
188        return true;
189    }
190
191    // Delete a node from the tree
192    deleteNode(nodeToDelete: RedBlackTreeNode<T>): void {
193        // Find replacement node in BST
194        const findBSTReplacement = (node: RedBlackTreeNode<T>): RedBlackTreeNode<T> | null => {
195            // When node has 2 children, find successor
196            if (node.left && node.right) return findSuccessor(node.right);
197            // When leaf node
198            if (!node.left && !node.right) return null;
199            // When single child
200            return node.left ?? node.right;
201        };
202
203        // Find the leftmost node in right subtree
204        const findSuccessor = (node: RedBlackTreeNode<T>): RedBlackTreeNode<T> => {
205            let current = node;
206            while (current.left) current = current.left;
207            return current;
208        };
209
210        const replacementNode = findBSTReplacement(nodeToDelete);
211        const bothBlack = (replacementNode === null || replacementNode.color === 1) && nodeToDelete.color === 1;
212        const parentNode = nodeToDelete.parent!;
213
214        if (!replacementNode) {
215            // Node to delete is a leaf
216            if (nodeToDelete === this.root) {
217                this.root = null;
218            } else {
219                if (bothBlack) {
220                    // Both nodes are black - fix double black
221                    this.fixDoubleBlack(nodeToDelete);
222                } else {
223                    // One is red - make sibling red if exists
224                    if (nodeToDelete.sibling()) {
225                        nodeToDelete.sibling()!.color = 0;
226                    }
227                }
228                // Remove node from tree
229                if (nodeToDelete.isOnLeft()) {
230                    parentNode.left = null;
231                } else {
232                    parentNode.right = null;
233                }
234            }
235            return;
236        }
237
238        if (!nodeToDelete.left || !nodeToDelete.right) {
239            // Node has one child
240            if (nodeToDelete === this.root) {
241                // Node is root - copy replacement data and remove replacement
242                nodeToDelete.data = replacementNode.data;
243                nodeToDelete.left = nodeToDelete.right = null;
244            } else {
245                // Detach node and move replacement up
246                if (nodeToDelete.isOnLeft()) {
247                    parentNode.left = replacementNode;
248                } else {
249                    parentNode.right = replacementNode;
250                }
251                replacementNode.parent = parentNode;
252                if (bothBlack) {
253                    this.fixDoubleBlack(replacementNode);
254                } else {
255                    replacementNode.color = 1;
256                }
257            }
258            return;
259        }
260
261        // Node has two children - swap with successor and recurse
262        this.swapData(replacementNode, nodeToDelete);
263        this.deleteNode(replacementNode);
264    }
265
266    // Fix double black violation in Red-Black Tree
267    fixDoubleBlack(node: RedBlackTreeNode<T>): void {
268        if (node === this.root) return;
269
270        const siblingNode = node.sibling();
271        const parentNode = node.parent!;
272
273        if (!siblingNode) {
274            // No sibling - push double black up
275            this.fixDoubleBlack(parentNode);
276        } else {
277            if (siblingNode.color === 0) {
278                // Sibling is red
279                parentNode.color = 0;
280                siblingNode.color = 1;
281                if (siblingNode.isOnLeft()) {
282                    this.rotateRight(parentNode);
283                } else {
284                    this.rotateLeft(parentNode);
285                }
286                this.fixDoubleBlack(node);
287            } else {
288                // Sibling is black
289                if (siblingNode.hasRedChild()) {
290                    // At least one red child
291                    if (siblingNode.left && siblingNode.left.color === 0) {
292                        if (siblingNode.isOnLeft()) {
293                            // Left-left case
294                            siblingNode.left.color = siblingNode.color;
295                            siblingNode.color = parentNode.color;
296                            this.rotateRight(parentNode);
297                        } else {
298                            // Right-left case
299                            siblingNode.left.color = parentNode.color;
300                            this.rotateRight(siblingNode);
301                            this.rotateLeft(parentNode);
302                        }
303                    } else {
304                        if (siblingNode.isOnLeft()) {
305                            // Left-right case
306                            siblingNode.right!.color = parentNode.color;
307                            this.rotateLeft(siblingNode);
308                            this.rotateRight(parentNode);
309                        } else {
310                            // Right-right case
311                            siblingNode.right!.color = siblingNode.color;
312                            siblingNode.color = parentNode.color;
313                            this.rotateLeft(parentNode);
314                        }
315                    }
316                    parentNode.color = 1;
317                } else {
318                    // Two black children
319                    siblingNode.color = 0;
320                    if (parentNode.color === 1) {
321                        this.fixDoubleBlack(parentNode);
322                    } else {
323                        parentNode.color = 1;
324                    }
325                }
326            }
327        }
328    }
329
330    // Insert data into the tree
331    insert(data: T): boolean {
332        // Find position to insert
333        let parentNode = this.root;
334        while (parentNode) {
335            if (this.lessThan(data, parentNode.data)) {
336                if (!parentNode.left) break;
337                else parentNode = parentNode.left;
338            } else if (this.lessThan(parentNode.data, data)) {
339                if (!parentNode.right) break;
340                else parentNode = parentNode.right;
341            } else break;
342        }
343
344        // Create and insert new node
345        const newNode = new RedBlackTreeNode(data);
346        if (!parentNode) {
347            this.root = newNode;
348        } else if (this.lessThan(newNode.data, parentNode.data)) {
349            parentNode.left = newNode;
350        } else if (this.lessThan(parentNode.data, newNode.data)) {
351            parentNode.right = newNode;
352        } else {
353            // Duplicate value - increment count
354            parentNode.count++;
355            return false;
356        }
357        newNode.parent = parentNode;
358        this.fixAfterInsert(newNode);
359        return true;
360    }
361
362    // Search for a value based on predicate
363    search(predicate: (value: T) => boolean, direction: 'left' | 'right'): T | undefined {
364        let currentNode = this.root;
365        let resultNode = null;
366        while (currentNode) {
367            if (predicate(currentNode.data)) {
368                resultNode = currentNode;
369                currentNode = currentNode[direction];
370            } else {
371                currentNode = currentNode[direction === 'left' ? 'right' : 'left'];
372            }
373        }
374        return resultNode?.data;
375    }
376
377    // Find a node with given data
378    find(data: T): RedBlackTreeNode<T> | null {
379        let currentNode = this.root;
380        while (currentNode) {
381            if (this.lessThan(data, currentNode.data)) {
382                currentNode = currentNode.left;
383            } else if (this.lessThan(currentNode.data, data)) {
384                currentNode = currentNode.right;
385            } else break;
386        }
387        return currentNode ?? null;
388    }
389
390    // Get count of occurrences for a value
391    count(data: T): number {
392        const node = this.find(data);
393        return node ? node.count : 0;
394    }
395
396    // In-order traversal generator
397    *inOrder(rootNode: RedBlackTreeNode<T> = this.root!): Generator<T, undefined, void> {
398        if (!rootNode) return;
399        for (const value of this.inOrder(rootNode.left!)) yield value;
400        yield rootNode.data;
401        for (const value of this.inOrder(rootNode.right!)) yield value;
402    }
403
404    // Reverse in-order traversal generator
405    *reverseInOrder(rootNode: RedBlackTreeNode<T> = this.root!): Generator<T, undefined, void> {
406        if (!rootNode) return;
407        for (const value of this.reverseInOrder(rootNode.right!)) yield value;
408        yield rootNode.data;
409        for (const value of this.reverseInOrder(rootNode.left!)) yield value;
410    }
411}
412
413// TreeMap implementation using Red-Black Tree
414class TreeMap<K = number, V = unknown> {
415    private _size: number;
416    private tree: RedBlackTree<K>;
417    private map: Map<K, V> = new Map();
418    private compare: CompareFunction<K>;
419
420    constructor(
421        collection: Array<[K, V]> | CompareFunction<K> = [],
422        compareFunc: CompareFunction<K> = (left: K, right: K) => (left < right ? -1 : left > right ? 1 : 0),
423    ) {
424        if (typeof collection === 'function') {
425            compareFunc = collection;
426            collection = [];
427        }
428        this._size = 0;
429        this.compare = compareFunc;
430        this.tree = new RedBlackTree(compareFunc);
431        for (const [key, value] of collection) {
432            this.set(key, value);
433        }
434    }
435
436    // Get the size of the map
437    size(): number {
438        return this._size;
439    }
440
441    // Check if key exists
442    has(key: K): boolean {
443        return !!this.tree.find(key);
444    }
445
446    // Get value by key
447    get(key: K): V | undefined {
448        return this.map.get(key);
449    }
450
451    // Set key-value pair
452    set(key: K, value: V): boolean {
453        const insertSuccess = this.tree.insert(key);
454        this._size += insertSuccess ? 1 : 0;
455        this.map.set(key, value);
456        return insertSuccess;
457    }
458
459    // Delete key-value pair
460    delete(key: K): boolean {
461        const deleteSuccess = this.tree.deleteAll(key);
462        this._size -= deleteSuccess ? 1 : 0;
463        return deleteSuccess;
464    }
465
466    // Find smallest key >= target
467    ceil(target: K): [K, V] | undefined {
468        return this.toKeyValue(this.tree.search(key => this.compare(key, target) >= 0, 'left'));
469    }
470
471    // Find largest key <= target
472    floor(target: K): [K, V] | undefined {
473        return this.toKeyValue(this.tree.search(key => this.compare(key, target) <= 0, 'right'));
474    }
475
476    // Find smallest key > target
477    higher(target: K): [K, V] | undefined {
478        return this.toKeyValue(this.tree.search(key => this.compare(key, target) > 0, 'left'));
479    }
480
481    // Find largest key < target
482    lower(target: K): [K, V] | undefined {
483        return this.toKeyValue(this.tree.search(key => this.compare(key, target) < 0, 'right'));
484    }
485
486    // Get first (smallest) key-value pair
487    first(): [K, V] | undefined {
488        return this.toKeyValue(this.tree.inOrder().next().value);
489    }
490
491    // Get last (largest) key-value pair
492    last(): [K, V] | undefined {
493        return this.toKeyValue(this.tree.reverseInOrder().next().value);
494    }
495
496    // Remove and return first key-value pair
497    shift(): [K, V] | undefined {
498        const firstPair = this.first();
499        if (firstPair === undefined) return undefined;
500        this.delete(firstPair[0]);
501        return firstPair;
502    }
503
504    // Remove and return last key-value pair
505    pop(): [K, V] | undefined {
506        const lastPair = this.last();
507        if (lastPair === undefined) return undefined;
508        this.delete(lastPair[0]);
509        return lastPair;
510    }
511
512    // Convert key to key-value pair
513    private toKeyValue(key: K): [K, V];
514    private toKeyValue(key: undefined): undefined;
515    private toKeyValue(key: K | undefined): [K, V] | undefined;
516    private toKeyValue(key: K | undefined): [K, V] | undefined {
517        return key != null ? [key, this.map.get(key)!] : undefined;
518    }
519
520    // Iterator for key-value pairs
521    *[Symbol.iterator](): Generator<[K, V], void, void> {
522        for (const key of this.keys()) {
523            yield this.toKeyValue(key);
524        }
525    }
526
527    // Generator for keys in ascending order
528    *keys(): Generator<K, void, void> {
529        for (const key of this.tree.inOrder()) {
530            yield key;
531        }
532    }
533
534    // Generator for values in key ascending order
535    *values(): Generator<V, undefined, void> {
536        for (const key of this.keys()) {
537            yield this.map.get(key)!;
538        }
539        return undefined;
540    }
541
542    // Generator for keys in descending order
543    *rkeys(): Generator<K, undefined, void> {
544        for (const key of this.tree.reverseInOrder()) {
545            yield key;
546        }
547        return undefined;
548    }
549
550    // Generator for values in key descending order
551    *rvalues(): Generator<V, undefined, void> {
552        for (const key of this.rkeys()) {
553            yield this.map.get(key)!;
554        }
555        return undefined;
556    }
557}
558
559// Calendar booking system using TreeMap
560class MyCalendar {
561    private treeMap: TreeMap<number, number>;
562
563    constructor() {
564        // TreeMap stores intervals as (endTime -> startTime)
565        this.treeMap = new TreeMap<number, number>();
566    }
567
568    // Book a time interval [startTime, endTime)
569    book(startTime: number, endTime: number): boolean {
570        // Find the first interval with end time > startTime
571        const nextInterval = this.treeMap.higher(startTime);
572      
573        // Check if there's an overlap with the next interval
574        // nextInterval[0] is endTime, nextInterval[1] is startTime of that interval
575        if (nextInterval && nextInterval[1] < endTime) {
576            return false; // Overlap detected
577        }
578      
579        // No overlap, add the new interval
580        this.treeMap.set(endTime, startTime);
581        return true;
582    }
583}
584

Time and Space Complexity

Time Complexity: O(n × log n) where n is the number of bookings made.

The book method performs the following operations:

  • self.sd.bisect_right(start): This performs a binary search on the sorted keys, taking O(log n) time.
  • self.sd.values()[idx]: Accessing values by index in a SortedDict takes O(log n) time as it needs to traverse the underlying tree structure.
  • self.sd[end] = start: Insertion into a SortedDict maintains sorted order and takes O(log n) time.

Since each booking operation takes O(log n) time and we can make up to n bookings, the total time complexity across n operations is O(n × log n).

Space Complexity: O(n) where n is the number of successful bookings.

The SortedDict stores one key-value pair for each successful booking. In the worst case where all n booking attempts are successful, the space required is O(n) to store all the intervals.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrectly Understanding the Overlap Check Logic

Pitfall: Many developers get confused about why we use bisect_right(start) and what exactly we're checking. A common mistake is thinking we need to check multiple intervals or all intervals that could potentially overlap.

Why it happens: The logic of storing {endTime: startTime} and using bisect_right on the start value can be counterintuitive at first glance.

Solution: Remember that bisect_right(start) finds the first interval whose endTime > start. This is the only interval we need to check because:

  • If this interval doesn't overlap, no subsequent intervals will (they have even later end times)
  • Any previous intervals have endTime ≤ start, so they can't overlap with [start, end)

2. Checking the Wrong Direction for Overlaps

Pitfall: After finding the candidate interval at index idx, developers might check the wrong condition, such as self.sorted_intervals.keys()[idx] < start instead of self.sorted_intervals.values()[idx] < end.

Example of incorrect check:

# WRONG: This doesn't properly detect overlaps
if index < len(self.sorted_intervals) and self.sorted_intervals.keys()[index] < end:
    return False

Solution: The correct overlap condition requires checking if the found interval's startTime (stored as value) is less than our new interval's end:

# CORRECT: Check if the found interval starts before our interval ends
if index < len(self.sorted_intervals) and self.sorted_intervals.values()[index] < end:
    return False

3. Forgetting to Handle Edge Cases

Pitfall: Not properly handling the case when bisect_right returns an index equal to the length of the dictionary (meaning all existing intervals end before or at start).

Solution: Always check index < len(self.sorted_intervals) before accessing the values. If this condition is false, it means all existing intervals end before the new interval starts, so there's no overlap.

4. Using Regular Dictionary Instead of SortedDict

Pitfall: Using a standard Python dict and trying to sort it manually, which breaks the O(log n) time complexity and makes the bisect operations invalid.

# WRONG: Regular dict doesn't maintain sorted order
self.intervals = {}  # This won't work with bisect_right

Solution: Always use SortedDict from the sortedcontainers library or implement your own balanced BST to maintain sorted order automatically:

from sortedcontainers import SortedDict
self.sorted_intervals = SortedDict()

5. Misunderstanding Half-Open Intervals

Pitfall: Treating the interval as [start, end] (closed) instead of [start, end) (half-open), leading to incorrect overlap detection for adjacent intervals.

Example: Events [1, 3) and [3, 5) should NOT overlap because the first ends at 3 (exclusive) and the second starts at 3 (inclusive).

Solution: Remember that the interval is half-open. Two intervals [a, b) and [c, d) overlap if and only if a < d AND c < b. The current implementation correctly handles this by checking if the found interval's start is less than our end.

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Recommended Readings

Segment Tree

Segment Tree Faster Range Queries For this article we want to introduce the idea of a Segment Tree Segment Trees allow us to quickly perform range queries as well as range updates Suppose we have an array and we want to know the sum of a particular range of numbers as well

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More