Intervals - My Calendar I

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.

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

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.

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)