My Calendar I

Share

Implement a calendar class. Method book(start, end) books a new event [start, end). Return true if it can be booked without overlap with existing events, false otherwise.

Example 1
book(10,20)→true, book(15,25)→false (overlaps), book(20,30)→true

Solution Approach

Use a TreeMap to store booked intervals. For each new event, check the floor entry (might overlap from left) and ceiling entry (might overlap from right).

  • TreeMap calendar.
  • For book(start,end): find floor key <= start; check if floor.end > start (overlap).
  • Find ceiling key >= start; check if ceil.start < end (overlap).
  • If no overlap: calendar.put(start,end), return true. Else return false.
Java
import java.util.*;

class MyCalendar {
    TreeMap<Integer,Integer> cal = new TreeMap<>();

    public boolean book(int start, int end) {
        Map.Entry<Integer,Integer> prev = cal.floorEntry(start);
        Map.Entry<Integer,Integer> next = cal.ceilingEntry(start);
        if ((prev == null || prev.getValue() <= start) &&
            (next == null || next.getKey() >= end)) {
            cal.put(start, end);
            return true;
        }
        return false;
    }
}
  • Time Complexity: book: O(log N)
  • Space Complexity: O(N)