Hey there 👋
Hope you are doing well 😃
In this blog we are going to see the complete intuition behind Leetcode problem 729. My Calendar I. We are to understand problem statement first then we will look at the solution of the problem followed by code.
Problem link -: https://leetcode.com/problems/my-calendar-i/description/
Let’s get started 🔥
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
Problem Explanation
The problem is about implementing a calendar which holds event for a particular time interval.
The calendar is implemented such that a single interval can hold single booking. For example suppose a user has made booking for time interval [1,4] then this complete slot will be assigned to this user now an another user comes to get a slot of [2,3], but he won’t be able to get it because this interval comes in [1,4].
Note that the slot represents a booking on the half-open interval [start, end), the range of real numbers x such that start <= x < end.
In this problem we are given a list of time intervals and we have to check that whether a time slot can be assigned to an event or not.
Approach
In the given problem the events can be booked in any order. For example [[47,50],[33,41]].
So here simply adding the possible slots in a set or map and checking the next slot with previous stored slots won’t give us desired solution.
Now what can we do here?🤔
In this problem we have to find a way through which we can ensure that a single event is assigned to every slot. This we can do using prefix sum and ordered map. Huh?🙄
We will make an ordered map (as it keep entries in sorted order). Whenever a slot is to be booked we will assume that the slot is valid and will book an event between start and end . mp[start]++ will indicate the starting point of event and mp[end]-- will indicate that the event has been completed at time end-1 . In this way we are keeping track of event in a particular time interval.
Now we will see in map that every slot has single booking. We will do it by calculating cumulative sum. Whenever sum>1 it shows that a double booking has been done. We will remove that time slot from map.
Note that the slot for which double booking is encountered is our current slot and this proves our assumption to be wrong.
As you can see here how the approach is keeping track of slot and booking.
And this is why I told you that the problem can be solved using map and prefix sum.
Code
Here we have made an ordered map and in book() method we have assumed that the current slot can be booked. Then we have calculated cumulative sum, if sum>1 it indicates a double booking and hence our assumption is wrong we will remove this entry from map and will return False . If everything works well we will return True .
So this was complete solution to problem 729. My Calendar I. I hope you have understood it well.
If you like the blog please leave some ❤
Thankyou 😃
Top comments (0)