Table of Contents
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