Skip to content

732. My Calendar III 👍

  • Time: $O(n\log n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class MyCalendarThree {
 public:
  int book(int start, int end) {
    ++timeline[start];
    --timeline[end];

    int ans = 0;
    int activeEvents = 0;

    for (const auto& [_, count] : timeline) {
      activeEvents += count;
      ans = max(ans, activeEvents);
    }

    return ans;
  }

 private:
  map<int, int> timeline;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class MyCalendarThree {
  public int book(int start, int end) {
    timeline.merge(start, 1, Integer::sum);
    timeline.merge(end, -1, Integer::sum);

    int ans = 0;
    int activeEvents = 0;

    for (final int count : timeline.values()) {
      activeEvents += count;
      ans = Math.max(ans, activeEvents);
    }

    return ans;
  }

  private Map<Integer, Integer> timeline = new TreeMap<>();
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
from sortedcontainers import SortedDict


class MyCalendarThree:
  def __init__(self):
    self.timeline = SortedDict()

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

    ans = 0
    activeEvents = 0

    for count in self.timeline.values():
      activeEvents += count
      ans = max(ans, activeEvents)

    return ans