Problem Description

The My Calendar III problem asks you to design a calendar system that can handle multiple event bookings and efficiently return the maximum number of overlapping events (the "k-booking") after each new booking.

• Implement a class MyCalendarThree with a function book(start, end).
• Each call to book(start, end) represents booking an event from time start (inclusive) to end (exclusive).
• After each booking, return the maximum number of events that overlap at any time (i.e., the maximum number of concurrent events).
• Constraints:
  • Events may overlap arbitrarily.
  • 1 ≤ start < end ≤ 10⁹
  • At most 400 calls to book.

The focus is on efficiently tracking and updating the maximum overlap as new bookings are made, without reusing or modifying previous bookings.

Thought Process

At first glance, you might consider storing every interval and, for each new booking, checking how many current bookings overlap with it. However, this brute-force approach becomes inefficient as the number of bookings increases.

The key insight is that we don't need to know exactly which events overlap at every moment; instead, we just need to track the number of overlapping events at any given time. This leads to the idea of using a sweep line algorithm, which is a common approach for interval and overlap problems.

• Instead of storing intervals, we track the change in the number of active events at every start and end point.
• By "sweeping" through all time points in order, we can efficiently determine the maximum number of concurrent events.
• This approach is much more scalable and avoids repeated overlap checks.

Solution Approach

To solve this problem efficiently, we use a sweep line technique with a time-point map (often a TreeMap or SortedDict), which tracks the net change in active events at each time.

1. Track changes at time points:
   • For each booking (start, end), increment the count at start and decrement the count at end in a map or dictionary.
2. Calculate overlaps:
   • To find the maximum overlap, iterate through time points in order, maintaining a running sum of active events, and update the maximum as you go.
3. Implementation details:
   • Since the number of bookings is small (≤ 400), it's efficient enough to scan all time points after each booking.
   • We use a data structure that keeps keys sorted (like SortedDict in Python, TreeMap in Java, or map in C++).

This approach avoids checking for overlaps directly and leverages the cumulative changes at event boundaries for efficiency.

Example Walkthrough

Consider the following sequence of bookings:

• book(10, 20) → returns 1
• book(50, 60) → returns 1
• book(10, 40) → returns 2
• book(5, 15) → returns 3
• book(5, 10) → returns 3
• book(25, 55) → returns 3

Let's analyze book(5, 15):

1. Increment at 5 (+1), decrement at 15 (-1).
2. Current map: {5: +1, 10: +2, 15: -1, 20: -1, 40: -1, 50: +1, 55: -1, 60: -1}
3. Sweep through the times in order, maintaining a running sum:
   • At 5: sum = 1
   • At 10: sum = 3
   • At 15: sum = 2
   • At 20: sum = 1
   • At 40: sum = 0
   • At 50: sum = 1
   • At 55: sum = 0
   • At 60: sum = -1
4. The maximum sum is 3, so we return 3.

This process is repeated for each booking.

Time and Space Complexity

• Brute-force approach:
  • For each booking, check overlap with all previous bookings.
  • Time complexity: O(N²) for N bookings.
  • Space complexity: O(N) for storing intervals.
• Optimized sweep line approach:
  • Each book updates two entries in the map/dictionary.
  • After each booking, we iterate over all unique time points (at most 2N).
  • Time complexity: O(N log N) per booking (for sorting/ordered traversal), O(N) if using a structure that maintains order.
  • Space complexity: O(N) for storing time points.
• Why? The sweep line leverages the fact that only event boundaries matter, so we process at most 2N points, which is efficient for N ≤ 400.

Summary

The sweep line algorithm efficiently solves the My Calendar III problem by tracking the net change in active events at each time point. By processing only the event boundaries and maintaining a running count, we avoid unnecessary overlap checks and achieve a solution that is both intuitive and performant. The approach is elegant because it leverages a simple data structure and a classic algorithmic paradigm to handle a potentially complex overlap scenario.

Code Implementation

from collections import defaultdict

class MyCalendarThree:
    def __init__(self):
        self.timeline = defaultdict(int)
        self.max_k = 0

    def book(self, start: int, end: int) -> int:
        self.timeline[start] += 1
        self.timeline[end] -= 1

        current = 0
        max_overlap = 0
        for time in sorted(self.timeline):
            current += self.timeline[time]
            max_overlap = max(max_overlap, current)
        self.max_k = max(self.max_k, max_overlap)
        return self.max_k
      

#include <map>
using namespace std;

class MyCalendarThree {
public:
    map<int, int> timeline;
    int max_k = 0;

    MyCalendarThree() {}

    int book(int start, int end) {
        timeline[start]++;
        timeline[end]--;
        int current = 0, max_overlap = 0;
        for (auto &p : timeline) {
            current += p.second;
            if (current > max_overlap)
                max_overlap = current;
        }
        max_k = max(max_k, max_overlap);
        return max_k;
    }
};
      

import java.util.*;

class MyCalendarThree {
    private TreeMap<Integer, Integer> timeline;
    private int maxK;

    public MyCalendarThree() {
        timeline = new TreeMap<>();
        maxK = 0;
    }

    public int book(int start, int end) {
        timeline.put(start, timeline.getOrDefault(start, 0) + 1);
        timeline.put(end, timeline.getOrDefault(end, 0) - 1);

        int current = 0, maxOverlap = 0;
        for (int delta : timeline.values()) {
            current += delta;
            maxOverlap = Math.max(maxOverlap, current);
        }
        maxK = Math.max(maxK, maxOverlap);
        return maxK;
    }
}
      

class MyCalendarThree {
    constructor() {
        this.timeline = {};
        this.maxK = 0;
    }

    book(start, end) {
        this.timeline[start] = (this.timeline[start] || 0) + 1;
        this.timeline[end] = (this.timeline[end] || 0) - 1;

        let current = 0, maxOverlap = 0;
        const times = Object.keys(this.timeline).map(Number).sort((a, b) => a - b);
        for (let time of times) {
            current += this.timeline[time];
            maxOverlap = Math.max(maxOverlap, current);
        }
        this.maxK = Math.max(this.maxK, maxOverlap);
        return this.maxK;
    }
}