291. My Calendar II

Keep two lists: all booked intervals, and the intervals that are already double-booked (overlaps). A new event is rejected only if it overlaps any double-booked interval (that would make a triple). Otherwise add it, and record its overlaps with existing bookings as new double-booked intervals.

Two levels of overlap

Maintain:

• booked — every accepted interval.
• overlaps — the intervals currently covered twice.

When book(start, end) arrives:

1. If [start, end) intersects any interval in overlaps, that point would be booked three times → return false.
2. Otherwise, for every interval in booked it intersects, add the intersection [max(starts), min(ends)) to overlaps (now double-booked).
3. Append [start, end) to booked and return true.

Two half-open intervals [a, b) and [c, d) intersect iff a < d and c < b.

Worked example

Bookings [10,20],[50,60],[10,40],[5,15],[5,10],[25,55]:

• [10,20] ✓; [50,60] ✓; [10,40] ✓ (double-books [10,20]); [5,15] ✗ (would triple-book [10,15]); [5,10] ✓; [25,55] ✓.

Results: [true, true, true, false, true, true].

Complexity

• Time: O(n) per book (scan existing intervals) → O(n^2) total.
• Space: O(n).

import java.util.*;

class MyCalendarTwo {
    private List<int[]> booked;
    private List<int[]> overlaps;

    public MyCalendarTwo() {
        booked = new ArrayList<>();
        overlaps = new ArrayList<>();
    }

    public boolean book(int start, int end) {
        for (int[] o : overlaps) {
            if (start < o[1] && o[0] < end) return false;
        }
        for (int[] b : booked) {
            if (start < b[1] && b[0] < end) {
                overlaps.add(new int[]{Math.max(start, b[0]), Math.min(end, b[1])});
            }
        }
        booked.add(new int[]{start, end});
        return true;
    }
}