Approach #1: Boundary Count [Accepted]

Intuition and Algorithm

When booking a new event [start, end), count delta[start]++ and delta[end]--. When processing the values of delta in sorted order of their keys, the largest such value is the answer.

In Python, we sort the set each time instead, as there is no analog to TreeMap available.

Complexity Analysis

  • Time Complexity: , where is the number of events booked. For each new event, we traverse delta in time. In Python, this is owing to the extra sort step.

  • Space Complexity: , the size of delta.


Analysis written by: @awice. Solution in Approach #2 inspired by @cchao.