My Calendar II

medium intervals design sweep line

Problem

Design MyCalendarTwo where book(start, end) adds a half-open interval and returns true only if doing so will never cause a triple booking. Reject the booking otherwise.

Inputbook(10,20); book(50,60); book(10,40); book(5,15)

Output[true, true, true, false]

The fourth booking would create a triple overlap with the first and third.

input

class MyCalendarTwo:
    def __init__(self):
        self.events = []
        self.overlaps = []
    def book(self, start, end):
        for s, e in self.overlaps:
            if start < e and s < end: return False
        for s, e in self.events:
            if start < e and s < end:
                self.overlaps.append((max(s, start), min(e, end)))
        self.events.append((start, end))
        return True

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

class MyCalendarTwo {
  List<int[]> events = new ArrayList<>(), overlaps = new ArrayList<>();
  public boolean book(int start, int end) {
    for (int[] x : overlaps) if (start < x[1] && x[0] < end) return false;
    for (int[] x : events) if (start < x[1] && x[0] < end)
      overlaps.add(new int[]{Math.max(x[0], start), Math.min(x[1], end)});
    events.add(new int[]{start, end});
    return true;
  }
}

class MyCalendarTwo {
  vector<pair<int,int>> events, overlaps;
public:
  bool book(int start, int end) {
    for (auto& [s, e] : overlaps) if (start < e && s < end) return false;
    for (auto& [s, e] : events) if (start < e && s < end)
      overlaps.push_back({max(s, start), min(e, end)});
    events.push_back({start, end});
    return true;
  }
};

Explanation

Here we may allow an event to overlap once (a double booking), but we must reject anything that would create a triple booking. The clever idea is to track two separate lists: all booked events, and the smaller regions that are already double-booked (covered by two events).

When a new event arrives, we first ask: does it overlap any region in overlaps? If yes, adding it would stack a third event on that spot, making a triple booking, so we return false.

If it clears that test, we accept it. But before storing it we compute its overlap with every existing event and record each such intersection — (max(s, start), min(e, end)) — into overlaps. These new double-booked regions guard against future triples.

Example: [10,20) and [50,60) are accepted with no overlaps. Then [10,40) is accepted and creates a double region [10,20). Finally [5,15) is rejected because it touches that double region, which would make times 10..15 triple-booked.

This works because a triple booking can only happen where two events already overlap, so checking the new event against just the overlap regions is enough.

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