731. My Calendar II LeetCode Solution

In this guide, you will get 731. My Calendar II LeetCode Solution with the best time and space complexity. The solution to My Calendar II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
My Calendar II solution in C++
My Calendar II solution in Java
My Calendar II solution in Python
Additional Resources

731. My Calendar II LeetCode Solution image

Problem Statement of My Calendar II

You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a triple booking.
A triple booking happens when three events have some non-empty intersection (i.e., some moment is common to all the three events.).
The event can be represented as a pair of integers startTime and endTime that represents a booking on the half-open interval [startTime, endTime), the range of real numbers x such that startTime <= x < endTime.
Implement the MyCalendarTwo class:

MyCalendarTwo() Initializes the calendar object.
boolean book(int startTime, int endTime) Returns true if the event can be added to the calendar successfully without causing a triple booking. Otherwise, return false and do not add the event to the calendar.

Example 1:

Input
[“MyCalendarTwo”, “book”, “book”, “book”, “book”, “book”, “book”]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output
[null, true, true, true, false, true, true]

Explanation
MyCalendarTwo myCalendarTwo = new MyCalendarTwo();
myCalendarTwo.book(10, 20); // return True, The event can be booked.
myCalendarTwo.book(50, 60); // return True, The event can be booked.
myCalendarTwo.book(10, 40); // return True, The event can be double booked.
myCalendarTwo.book(5, 15); // return False, The event cannot be booked, because it would result in a triple booking.
myCalendarTwo.book(5, 10); // return True, The event can be booked, as it does not use time 10 which is already double booked.
myCalendarTwo.book(25, 55); // return True, The event can be booked, as the time in [25, 40) will be double booked with the third event, the time [40, 50) will be single booked, and the time [50, 55) will be double booked with the second event.

Constraints:

0 <= start < end <= 109
At most 1000 calls will be made to book.

Complexity Analysis

Time Complexity: O(n^2)
Space Complexity: O(n)

731. My Calendar II LeetCode Solution in C++

class MyCalendarTwo {
 public:
  bool book(int start, int end) {
    for (const auto& [s, e] : overlaps)
      if (max(start, s) < min(end, e))
        return false;

    for (const auto& [s, e] : ranges) {
      const int ss = max(start, s);
      const int ee = min(end, e);
      if (ss < ee)
        overlaps.emplace_back(ss, ee);
    }

    ranges.emplace_back(start, end);
    return true;
  }

 private:
  vector<pair<int, int>> ranges;
  vector<pair<int, int>> overlaps;
};
/* code provided by PROGIEZ */

731. My Calendar II LeetCode Solution in Java

class MyCalendarTwo {
  public boolean book(int start, int end) {
    for (int[] overlap : overlaps)
      if (Math.max(start, overlap[0]) < Math.min(end, overlap[1]))
        return false;

    for (int[] range : ranges) {
      final int maxStart = Math.max(start, range[0]);
      final int minEnd = Math.min(end, range[1]);
      if (maxStart < minEnd)
        overlaps.add(new int[] {maxStart, minEnd});
    }

    ranges.add(new int[] {start, end});
    return true;
  }

  List<int[]> ranges = new ArrayList<>();
  List<int[]> overlaps = new ArrayList<>();
}
// code provided by PROGIEZ

731. My Calendar II LeetCode Solution in Python

class MyCalendarTwo {
 public:
  bool book(int start, int end) {
    ++timeline[start];
    --timeline[end];

    int activeEvents = 0;

    for (const auto& [_, count] : timeline) {
      activeEvents += count;
      if (activeEvents > 2) {
        if (--timeline[start] == 0)
          timeline.erase(start);
        if (++timeline[end] == 0)
          timeline.erase(end);
        return false;
      }
    }

    return true;
  }

 private:
  map<int, int> timeline;
};
 # code by PROGIEZ