Calendar Systems: Overlap Detection

My Calendar I (LeetCode 729)

Implement a book(start, end) function that adds an event [start, end) to your calendar if it doesn't overlap with any existing events.

Strategy: TreeMap (Recommended)

In Java, TreeMap allows us to find the closest intervals to our current start in $O(\log N)$ time.

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

    public boolean book(int start, int end) {
        // Find the event that starts at or before 'start'
        Map.Entry<Integer, Integer> prev = calendar.floorEntry(start);
        // Find the event that starts at or after 'start'
        Map.Entry<Integer, Integer> next = calendar.ceilingEntry(start);
        
        // No overlap with prev: prev.end <= start
        // No overlap with next: end <= next.start
        if ((prev == null || prev.getValue() <= start) &&
            (next == null || end <= next.getKey())) {
            calendar.put(start, end);
            return true;
        }
        return false;
    }
}

Complexity: $O(\log N)$ per booking, $O(N)$ space.

My Calendar II (LeetCode 731)

Allows "double booking" but prohibits "triple booking."

Strategy: Two-Layer Intersection

Maintain two lists: recorded (all events) and overlaps (intersections where double booking has already occurred).

class MyCalendarTwo {
    private List<int[]> recorded = new ArrayList<>();
    private List<int[]> overlaps = new ArrayList<>();

    public boolean book(int start, int end) {
        // If the new range overlaps with an existing double-booking, it's a triple-booking
        for (int[] range : overlaps) {
            if (Math.max(start, range[0]) < Math.min(end, range[1])) return false;
        }
        
        // Calculate new overlaps with current recorded events
        for (int[] range : recorded) {
            int intersectStart = Math.max(start, range[0]);
            int intersectEnd = Math.min(end, range[1]);
            if (intersectStart < intersectEnd) {
                overlaps.add(new int[]{intersectStart, intersectEnd});
            }
        }
        recorded.add(new int[]{start, end});
        return true;
    }
}

My Calendar III (LeetCode 732)

Track the maximum $K$-booking (maximum number of overlapping events) at any point in time.

Strategy: Sweep-Line (Difference Array)

Use a TreeMap to store "events" as points in time. A start adds 1 to the overlap count, and an end subtracts 1.

class MyCalendarThree {
    private TreeMap<Integer, Integer> timeline = new TreeMap<>();

    public int book(int start, int end) {
        timeline.put(start, timeline.getOrDefault(start, 0) + 1);
        timeline.put(end, timeline.getOrDefault(end, 0) - 1);
        
        int kMax = 0, currentActive = 0;
        // Sweep across time in order
        for (int delta : timeline.values()) {
            currentActive += delta;
            if (currentActive > kMax) kMax = currentActive;
        }
        return kMax;
    }
}

Complexity: $O(N)$ per booking to sweep the map. Can be optimized to $O(\log N)$ with a Segment Tree.

Summary Summary Table