Scale Engineer

My Calendar II

Med
#0685Time: O(N^3) for N calls. The k-th call takes O(k^2) time because the number of overlaps can be O(k^2). The total time is the sum of k^2 for k from 1 to N.Space: O(N^2), where N is the number of bookings. The `bookings` list stores N events, but the `overlaps` list can store up to O(N^2) intervals.
Patterns
DesignPrefix Sum
Algorithms
Binary Search
Data structures
ArraySegment TreeOrdered Set

Prompt

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 <= 109
  • At most 1000 calls will be made to book.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach maintains two lists: one for all booked events (bookings) and another for all double-booked time intervals (overlaps). When a new event is to be booked, we first check if it intersects with any of the existing double-booked intervals. If it does, it would create a triple booking, so we reject the event. If it doesn't, we accept the event, add it to our bookings list, and then update the overlaps list by checking the new event against all previously booked events.

Algorithm

  • Initialize two lists, bookings to store all events and overlaps to store all double-booked intervals.
  • When book(start, end) is called:
    1. Iterate through each interval o in the overlaps list. If the new event [start, end) intersects with o, it would create a triple booking. Return false.
    2. If no triple booking is found, iterate through the bookings list. For each existing event b, calculate the intersection with [start, end). If the intersection is non-empty, add it to the overlaps list.
    3. Add the new event [start, end) to the bookings list.
    4. Return true.

Walkthrough

We initialize two lists, bookings and overlaps. For each book(start, end) call:

  1. Check for Triple Booking: Iterate through the overlaps list. For each interval [o_start, o_end) in overlaps, check if it intersects with the new event [start, end). An intersection occurs if start < o_end and end > o_start. If an intersection is found, it means a triple booking would occur. We return false immediately.

  2. Update Overlaps: If no triple booking is detected, we proceed to add the event. But first, we must identify any new double-booked intervals created by this new event. We iterate through the bookings list. For each existing event [b_start, b_end), we calculate its intersection with [start, end). The intersection is [max(start, b_start), min(end, b_end)). If this intersection is non-empty (i.e., the start is less than the end), we add this new double-booked interval to the overlaps list.

  3. Add Event: After updating the overlaps, we add the new event [start, end) to the bookings list.

  4. Return true to indicate a successful booking.

class MyCalendarTwo {    private List<int[]> bookings;    private List<int[]> overlaps;     public MyCalendarTwo() {        bookings = new ArrayList<>();        overlaps = new ArrayList<>();    }     public boolean book(int start, int end) {        for (int[] o : overlaps) {            if (start < o[1] && end > o[0]) {                return false; // Triple booking            }        }         for (int[] b : bookings) {            int overlapStart = Math.max(start, b[0]);            int overlapEnd = Math.min(end, b[1]);            if (overlapStart < overlapEnd) {                overlaps.add(new int[]{overlapStart, overlapEnd});            }        }         bookings.add(new int[]{start, end});        return true;    }}

Complexity

Time

O(N^3) for N calls. The k-th call takes O(k^2) time because the number of overlaps can be O(k^2). The total time is the sum of k^2 for k from 1 to N.

Space

O(N^2), where N is the number of bookings. The `bookings` list stores N events, but the `overlaps` list can store up to O(N^2) intervals.

Trade-offs

Pros

  • Conceptually straightforward and relatively easy to implement.

Cons

  • Highly inefficient O(N^3) time complexity for N calls.

  • High space complexity of O(N^2).

Solutions

class MyCalendarTwo { private Map < Integer , Integer > tm = new TreeMap <>(); public MyCalendarTwo () { } public boolean book ( int start , int end ) { tm . put ( start , tm . getOrDefault ( start , 0 ) + 1 ); tm . put ( end , tm . getOrDefault ( end , 0 ) - 1 ); int s = 0 ; for ( int v : tm . values ()) { s += v ; if ( s > 2 ) { tm . put ( start , tm . get ( start ) - 1 ); tm . put ( end , tm . get ( end ) + 1 ); return false ; } } return true ; } } /** * Your MyCalendarTwo object will be instantiated and called as such: * MyCalendarTwo obj = new MyCalendarTwo(); * boolean param_1 = obj.book(start,end); */

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem