Scale Engineer

My Calendar I

Med
#0683Time: O(N) per `book` call. For `k` existing bookings, we iterate through all `k` of them. Since there can be up to `N` calls, the `k`-th call can take O(k) time. The total time for `N` calls is O(N^2).Space: O(N), where N is the number of successful bookings. We need to store each booked event.1 company
Patterns
Design
Algorithms
Binary SearchSkip List
Data structures
ArraySegment TreeOrdered Set
Companies
Flexport

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 double booking.

A double booking happens when two events have some non-empty intersection (i.e., some moment is common to both 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 MyCalendar class:

  • MyCalendar() 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 double booking. Otherwise, return false and do not add the event to the calendar.

 

Example 1:

Input
["MyCalendar", "book", "book", "book"]
[[], [10, 20], [15, 25], [20, 30]]
Output
[null, true, false, true]

Explanation
MyCalendar myCalendar = new MyCalendar();
myCalendar.book(10, 20); // return True
myCalendar.book(15, 25); // return False, It can not be booked because time 15 is already booked by another event.
myCalendar.book(20, 30); // return True, The event can be booked, as the first event takes every time less than 20, but not including 20.

 

Constraints:

  • 0 <= start < end <= 109
  • At most 1000 calls will be made to book.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses a simple list to store all the booked events. For each new booking request, it iterates through the entire list of existing events to check for any overlaps. While straightforward, its performance degrades as the number of events increases.

Algorithm

  • Initialize a list, bookings, to store the event intervals [start, end).
  • When book(start, end) is called, iterate through every event b already in the bookings list.
  • For each event b = [s, e), check if the new event [start, end) overlaps with it. The condition for an overlap is start < e and s < end. A more concise way to check this is Math.max(start, s) < Math.min(end, e).
  • If an overlap is found with any existing event, the new event cannot be booked. Return false immediately.
  • If the loop completes without finding any overlaps, the booking is valid. Add the new event [start, end) to the bookings list and return true.

Walkthrough

We maintain a simple ArrayList to store the event intervals. Each event is represented as an array of two integers, [startTime, endTime).

When the book(start, end) method is called, we perform a linear scan through our list of already booked events. For each existing event [s, e), we check if it has a non-empty intersection with the new event [start, end). Two half-open intervals [s1, e1) and [s2, e2) overlap if and only if s1 < e2 and s2 < e1.

If an overlap is detected with any event in the list, we know it's a double booking. We immediately return false and do not add the new event to the calendar. If we successfully iterate through the entire list without finding any conflicts, it signifies that the time slot is free. We then add the new event [start, end) to our list and return true.

import java.util.ArrayList;import java.util.List; class MyCalendar {    private List<int[]> bookings;     public MyCalendar() {        bookings = new ArrayList<>();    }     public boolean book(int start, int end) {        for (int[] b : bookings) {            // Check for overlap: max(start_A, start_B) < min(end_A, end_B)            if (Math.max(b[0], start) < Math.min(b[1], end)) {                return false;            }        }        bookings.add(new int[]{start, end});        return true;    }}

Complexity

Time

O(N) per `book` call. For `k` existing bookings, we iterate through all `k` of them. Since there can be up to `N` calls, the `k`-th call can take O(k) time. The total time for `N` calls is O(N^2).

Space

O(N), where N is the number of successful bookings. We need to store each booked event.

Trade-offs

Pros

  • Simple to understand and implement.

  • Requires minimal code and standard data structures.

Cons

  • Inefficient for a large number of bookings as the time for each book operation grows linearly with the number of events already in the calendar.

Solutions

import java.util.Map ; import java.util.TreeMap ; class MyCalendar { private final TreeMap < Integer , Integer > tm = new TreeMap <>(); public MyCalendar () { } public boolean book ( int start , int end ) { Map . Entry < Integer , Integer > ent = tm . floorEntry ( start ); if ( ent != null && ent . getValue () > start ) { return false ; } ent = tm . ceilingEntry ( start ); if ( ent != null && ent . getKey () < end ) { return false ; } tm . put ( start , end ); return true ; } } /** * Your MyCalendar object will be instantiated and called as such: MyCalendar * obj = new MyCalendar(); 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