Algorithm

Problem Name: 732. My Calendar III

Problem Link: https://leetcode.com/problems/my-calendar-iii/
 

A k-booking happens when k events have some non-empty intersection (i.e., there is some time that is common to all k events.)

You are given some events [startTime, endTime), after each given event, return an integer k representing the maximum k-booking between all the previous events.

Implement the MyCalendarThree class:

  • MyCalendarThree() Initializes the object.
  • int book(int startTime, int endTime) Returns an integer k representing the largest integer such that there exists a k-booking in the calendar.

 

Example 1:

Input
["MyCalendarThree", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output
[null, 1, 1, 2, 3, 3, 3]

Explanation
MyCalendarThree myCalendarThree = new MyCalendarThree();
myCalendarThree.book(10, 20); // return 1
myCalendarThree.book(50, 60); // return 1
myCalendarThree.book(10, 40); // return 2
myCalendarThree.book(5, 15); // return 3
myCalendarThree.book(5, 10); // return 3
myCalendarThree.book(25, 55); // return 3

 

Constraints:

  • 0 <= startTime < endTime <= 109
  • At most 400 calls will be made to book.

Code Examples

#1 Code Example with Java Programming

Code - Java Programming


class MyCalendarThree {
  
  private TreeMap delta;
  
  public MyCalendarThree() {
    this.delta = new TreeMap < >();
  }

  public int book(int start, int end) {
    delta.put(start, delta.getOrDefault(start, 0) + 1);
    delta.put(end, delta.getOrDefault(end, 0) - 1);
    int activeEvents = 0;
    int maxEvents = 0;
    for (int d : delta.values()) {
      activeEvents += d;
      maxEvents = Math.max(maxEvents, activeEvents);
    }
    return maxEvents;
  }
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
["MyCalendarThree", "book", "book", "book", "book", "book", "book"] [[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]

Output

x
–
+
cmd
[null, 1, 1, 2, 3, 3, 3]

#2 Code Example with Javascript Programming

Code - Javascript Programming


const find = (cals, time, count) => {
  let l = 0
  let r = cals.length
  let mid
  while (l < r) {
    mid = Math.trunc((l + r) / 2)
    if (cals[mid][0] === time) {
      cals[mid][1] += count
      return
    } else if (cals[mid][0] < time) {
      l = mid + 1
    } else {
      r = mid
    }
  }
  cals.splice(l, 0, [time, count])
}
const MyCalendarThree = function() {
  this.cals = []
}

MyCalendarThree.prototype.book = function(start, end) {
  let idx = find(this.cals, start, 1)
  idx = find(this.cals, end, -1)
  let count = 0
  let max = 0
  for (let cal of this.cals) {
    count += cal[1]
    max = Math.max(max, count)
  }
  return max
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
["MyCalendarThree", "book", "book", "book", "book", "book", "book"] [[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]

Output

x
–
+
cmd
[null, 1, 1, 2, 3, 3, 3]

#3 Code Example with Python Programming

Code - Python Programming


class MyCalendarThree:

    def __init__(self):
        self.times = []

    def book(self, start, end):
        bisect.insort(self.times, (start, 1))
        bisect.insort(self.times, (end, -1))
        res = cur = 0
        for _, x in self.times:
            cur += x
            res = max(res, cur)
        return res
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
["MyCalendarThree", "book", "book", "book", "book", "book", "book"] [[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]

Output

x
–
+
cmd
[null, 1, 1, 2, 3, 3, 3]
Advertisements

Demonstration

Previous
#731 Leetcode My Calendar II Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#733 Leetcode Flood Fill Solution in C, C++, Java, JavaScript, Python, C# Leetcode