13.5 My Calendar I

13.5.1 Problem Metadata

13.5.2 Description

Design a calendar that can add non-overlapping half-open intervals [start, end). The method book(start, end) should return true when the booking does not intersect any existing booking and false otherwise.

13.5.3 Examples

Input:
["MyCalendar","book","book","book"]
[[],[10,20],[15,25],[20,30]]

Output:
[null,true,false,true]

13.5.4 Constraints

  • 0 <= start < end <= 10^9
  • At most 1000 calls to book

13.5.5 Solution - Brute Force Interval Scan

13.5.5.1 Walkthrough

Keep a lc-list of existing bookings. To insert a new booking, compare it against every stored interval and reject it if any overlap occurs. Because the number of operations is bounded by 1000, a linear scan per request is acceptable.

13.5.5.2 Analysis

  • Time Complexity: O(n) per booking for n stored intervals
  • Space Complexity: O(n) to store the bookings

13.5.5.3 Implementation Steps

  1. Represent each booking with a Booking object holding start and end.
  2. For a new interval [s, e), iterate over existing bookings.
  3. If s < existing.end and e > existing.start, intervals overlap; reject.
  4. Otherwise append the interval and return true.

13.5.5.4 Code - Java

class Booking {
    int start;
    int end;

    Booking(int start, int end) {
        this.start = start;
        this.end = end;
    }

    boolean overlaps(Booking that) {
        return this.start < that.end && that.start < this.end;
    }
}

class MyCalendar {
    private final List<Booking> bookings = new ArrayList<>();

    public boolean book(int start, int end) {
        Booking request = new Booking(start, end);
        for (Booking existing : bookings) {
            if (existing.overlaps(request)) {
                return false;
            }
        }
        bookings.add(request);
        return true;
    }
}

13.5.6 Solution - TreeMap Boundary Search

13.5.6.1 Walkthrough

Store bookings inside a TreeMap keyed by start time. To book [start, end), find the neighbor with the greatest start less than end (using lowerKey) and ensure its end time is not greater than start. This works because overlapping intervals must have an earlier start that ends after the new start.

13.5.6.2 Analysis

  • Time Complexity: O(log n) per booking for TreeMap lookups and inserts
  • Space Complexity: O(n)

13.5.6.3 Implementation Steps

  1. Maintain TreeMap<Integer, Integer> bookings storing start -> end.
  2. For a request [s, e), find prevStart = bookings.lowerKey(e).
  3. If prevStart is null or bookings.get(prevStart) <= s, the booking fits.
  4. Insert [s, e) and return true; otherwise return false.

13.5.6.4 Code - Java

class MyCalendarTreeMap {
    private final TreeMap<Integer, Integer> bookings = new TreeMap<>();

    public boolean book(int start, int end) {
        Integer prevStart = bookings.lowerKey(end);
        if (prevStart == null || bookings.get(prevStart) <= start) {
            bookings.put(start, end);
            return true;
        }
        return false;
    }
}