My Calendar I

medium intervals binary search ordered set design

Problem

Design a MyCalendar that records events as half-open intervals [start, end). The book(start, end) call should add the event and return true only if it does not overlap any previously booked event.

Inputbook(10,20); book(15,25); book(20,30)

Output[true, false, true]

The second booking overlaps [10,20); the third only touches at 20 which is allowed.

input

from sortedcontainers import SortedList
class MyCalendar:
    def __init__(self):
        self.starts = SortedList()
        self.book_map = {}
    def book(self, start, end):
        i = self.starts.bisect_right(start)
        if i > 0 and self.book_map[self.starts[i-1]] > start: return False
        if i < len(self.starts) and self.starts[i] < end: return False
        self.starts.add(start); self.book_map[start] = end
        return True

class MyCalendar {
  constructor() { this.events = []; }
  book(start, end) {
    for (const [s, e] of this.events) if (start < e && s < end) return false;
    this.events.push([start, end]);
    return true;
  }
}

class MyCalendar {
  TreeMap<Integer,Integer> map = new TreeMap<>();
  public boolean book(int start, int end) {
    Integer prev = map.floorKey(start), next = map.ceilingKey(start);
    if (prev != null && map.get(prev) > start) return false;
    if (next != null && next < end) return false;
    map.put(start, end);
    return true;
  }
}

class MyCalendar {
  map<int,int> mp;
public:
  bool book(int start, int end) {
    auto it = mp.lower_bound(start);
    if (it != mp.end() && it->first < end) return false;
    if (it != mp.begin() && prev(it)->second > start) return false;
    mp[start] = end;
    return true;
  }
};

Explanation

The goal is to accept a new event only when it does not overlap any event we have already booked. The neat trick is to keep all bookings sorted by start time so we only have to check the one or two neighbours nearest to the new event, instead of scanning everything.

For a new [start, end), we find where start would slot into the sorted starts. We then look at just two candidates: the booking right before it and the booking right at that position. Using a half-open interval rule, two events clash only when one truly steps into the other.

The check is simple: if the previous booking's end is greater than our start, it spills into us, so reject. If the next booking's start is less than our end, we spill into it, so reject. Otherwise the slot is free, so we add start and remember its end.

Example: book [10,20) succeeds. Then [15,25) fails because the previous event ends at 20 which is past 15. Then [20,30) succeeds because the earlier event ends exactly at 20, and touching at the boundary is allowed.

Because the bookings stay sorted, finding the neighbours is a binary search, so each booking is fast even with many events.

Time: O(log n) per booking Space: O(n)