My Calendar I LeetCode Solution

Difficulty Level Medium
Frequently asked in Amazon Apple Bloomberg eBay Facebook Google Intuit Oracle QualtricsViews 2789

Problem Statement

My Calendar I LeetCode Solution –  We need to write a program that can be used as a 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:

Test Case 1:

Input:

[“MyCalendar”, “book”, “book”, “book”, “book”]

[[], [10,20], [20,30], [17, 18], [25,35]]

Output:

[null, true, true, false, false]

Explanation:

i) MyCalendar calendar = new MyCalendar();

ii) calendar.book(10, 20); // returns true as it does not coincide with any time range

iii) calendar.book(20, 30); // returns true as it does not coincide with any time range

iv) calendar.book(17, 18); // returns false as it coincides with the time range [10,20]

v) calendar.book(25, 35); // returns false as it coincides with the time range [20,30]

Approach

Idea:

The brute force solution is quite obvious. Whenever we book, we can traverse all the values in the calendar and check if the range coincides with any value. But it will take O(n^2) time. Here the time complexity is more because the searching takes O(n) time. So we can think of how to optimize it. We need to store the elements in sorted order so that we can search for the start and end value in O(logn) time which brings down the time complexity to O(nlogn) time.

In Java, we can use TreeMap and in C++ we can use Ordered Map for this.

Code

Java Program for My Calendar I LeetCode Solution

class MyCalendar {

    TreeMap<Integer, Integer> calendar;

    public MyCalendar() {
        calendar = new TreeMap<>();
    }

    public boolean book(int start, int end) {
        Integer lessThanStart = calendar.floorKey(start);
        if (lessThanStart != null && calendar.get(lessThanStart) > start) 
          return false;
      
        Integer greaterThanStart = calendar.ceilingKey(start);
        if (greaterThanStart != null && greaterThanStart < end) 
          return false;

        calendar.put(start, end);
        return true;
    }
}

C++ Program for My Calendar I LeetCode Solution

class MyCalendar {
map<int,int> calendar;
public:
    MyCalendar() {
        
    }
    
    bool book(int start, int end) {
        auto next = calendar.upper_bound(start);
        if(next != calendar.end() && (*next).second < end)
          return false;
        calendar.insert({end,start});
        return true;
    }
};

Complexity Analysis for My Calendar I LeetCode Solution

Time Complexity

Here we need to insert n events and to check if each event is legal or not, it will take O(logn) time. So the time complexity is O(nlogn).

Space Complexity

We are storing n events in a data structure. So the space complexity is O(n).

Reference: https://en.wikipedia.org/wiki/Calendar

 

 

 

 

 

 

 

 

 

 

 

 

Translate »