Last updated on January 13th, 2025 at 09:40 pm

Here, we see a My Calendar I LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Dynamic Programming, Minimax

Companies

Level of Question

Medium

My Calendar I LeetCode Solution

1. Problem Statement

You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a double booking.

A double booking happens when two events have some non-empty intersection (i.e., some moment is common to both events.).

The event can be represented as a pair of integers start and end that represents a booking on the half-open interval [start, end), the range of real numbers x such that start <= x < end.

Implement the MyCalendar class:

MyCalendar() Initializes the calendar object.
boolean book(int start, int end) Returns true if the event can be added to the calendar successfully without causing a double booking. Otherwise, return false and do not add the event to the calendar.

Example 1:
Input: [“MyCalendar”, “book”, “book”, “book”] [[], [10, 20], [15, 25], [20, 30]]
Output: [null, true, false, true]

Explanation:
MyCalendar myCalendar = new MyCalendar();
myCalendar.book(10, 20); // return True
myCalendar.book(15, 25); // return False, It can not be booked because time 15 is already booked by another event.
myCalendar.book(20, 30); // return True, The event can be booked, as the first event takes every time less than 20, but not including 20.

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is “Modified Binary Search”. This pattern is evident because the code uses binary search (or its equivalent) to efficiently find the correct position to insert a new interval while ensuring no overlap with existing intervals. The binary search is modified to handle the specific requirements of interval insertion and overlap checking.

3. Code Implementation in Different Languages

3.1 My Calendar I C++

class MyCalendar {
public:
    map<int, int> mp;
    MyCalendar() { 
    }
    bool book(int start, int end) {
        auto it = mp.upper_bound(start);
        if (it == mp.end() || it->second >= end)
        {
            mp[end] = start;
            return true;
        }
        else
            return false;        
    }
};

3.2 My Calendar I Java

class MyCalendar {
    TreeMap<Integer,Integer> calendar = new TreeMap<>();
    public MyCalendar() {
        calendar.put(Integer.MAX_VALUE, Integer.MAX_VALUE);
    }
    public boolean book(int start, int end) {
        Map.Entry<Integer,Integer> pair = calendar.higherEntry(start);
        boolean res = end <= pair.getValue();
        if (res) calendar.put(end, start);
        return res;
    }
}

3.3 My Calendar I JavaScript

var MyCalendar = function() {
  this.cal = []    
};
MyCalendar.prototype.book = function(start, end) {
    let l=0, r=this.cal.length-1
    while(l <= r){
      const mid = Math.floor((r+l)/2)
      const [s,e] = this.cal[mid]
      if(s < end && start < e ) return false
      if(start >= e){
        l = mid+1
      }else{
        r = mid-1
      }
    }
  this.cal.splice(l, 0 ,[start, end])
  return true    
};

3.4 My Calendar I Python

class MyCalendar(object):
    def __init__(self):
        self.calendar = []   
    def book(self, start, end):
        right = len(self.calendar)
        if right == 0:
            self.calendar.append((start, end))
            return True
        left = 0
        while left < right:
            mid = int(left + (right - left)/2)
            if self.calendar[mid][1] <= start:
                left = mid + 1
            else:
                right = mid
        if left == len(self.calendar):
            self.calendar.append((start, end))
            return True
        if self.calendar[left][0] >= end:
            self.calendar.insert(left, (start, end))
            return True
        return False

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(log n)	O(n)
Java	O(log n)	O(n)
JavaScript	O(n)	O(n)
Python	O(n)	O(n)

The coding pattern is Modified Binary Search.
C++ and Java implementations are more efficient due to their use of tree-based data structures.
JavaScript and Python implementations are less efficient due to the use of arrays/lists for storing intervals.