292. My Calendar III

Represent each event as +1 at its start and -1 at its end on a timeline. The maximum number of simultaneously-active events is the maximum running prefix sum over the sorted timeline. After each booking, recompute that maximum.

Difference array on a sorted timeline

Store a map delta[time] -> net change. Booking [start, end) does delta[start] += 1 and delta[end] -= 1.

The number of events active at any moment is the running sum of deltas up to that moment, so the maximum overlap is the maximum prefix sum when sweeping the times in sorted order:

book(start, end):
    delta[start] += 1; delta[end] -= 1
    cur = 0; best = 0
    for t in sorted(delta): cur += delta[t]; best = max(best, cur)
    return best

Worked example

Bookings [10,20],[50,60],[10,40],[5,15],[5,10],[25,55] return, after each, the running max overlap:

[1, 1, 2, 3, 3, 3] — the triple overlap first appears when [5,15] joins [10,20] and [10,40] around time [10,15].

Complexity

• Time: O(n log n) per book (re-sweeping the sorted timeline) → O(n^2 log n) total. A balanced-BST / segment tree can improve this.
• Space: O(n).

import java.util.*;

class MyCalendarThree {
    private TreeMap<Integer, Integer> delta;

    public MyCalendarThree() {
        delta = new TreeMap<>();
    }

    public int book(int startTime, int endTime) {
        delta.merge(startTime, 1, Integer::sum);
        delta.merge(endTime, -1, Integer::sum);
        int cur = 0, best = 0;
        for (int v : delta.values()) {
            cur += v;
            best = Math.max(best, cur);
        }
        return best;
    }
}