Last Updated: 1 Apr, 2021
My Calendar
Easy
Asked in companies
Given ‘N’ events each with a ‘start’ and ‘end’ time in the form of intervals such that it represents a booking on the half-open interval [start, end), i.e., the range of real numbers x such that start <= x < end. Initially, the calendar has no events. A new event can be added to the calendar, if adding the event will not cause a triple booking. A triple booking happens when three events have some non-empty intersection (i.e., there exists a time common to all the 3 events).
Your task is to process the 'N' events, and for each of the events, add that event to the calendar and return ‘True’, if the event can be added to the calendar successfully without causing a triple booking. Otherwise, return ‘False’ and do not add that event to the calendar.
Input format:
The first line of input contains an integer ‘T’, denoting the number of test cases.
The first line of each test case contains an integer ‘N’, which represents the total number of events.
Then the next ‘N’ lines contain two space-separated integers 'Start' and 'End', denoting the starting and ending times of the 'N' intervals.
Output format:
For each test case, print 'N' space-separated 'True' or 'False' denoting the status of each event. (‘True’ if the addition of an event to the calendar does not cause triple booking, ‘False’ otherwise).
Output for each test case is printed on a separate line.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given functions.
Constraints:
1 <= T <= 10
1 <= N <= 1000
0 <= Start , End <= 10^9
Time Limit: 1 sec
Approaches
- This is a brute force approach where we will maintain two lists.
- The first list will contain all the events that are booked at least once.
- The second list will contain all the events that cause conflicts exactly two times.
- So whenever a new event comes and if it conflicts with the double-booked events then it will cause triple booking and becomes invalid and we have to return ‘False’.
- Otherwise, we will check if it causes conflict with the existing events then we will add that event to the second list. Also, we will add that event to the first list and return ‘True’.
- Two events [S1, E1) & [S2, E2) cause conflict if S1 < E2 and E1 > S2.
Algorithm:
- Create two arrays ‘Events’ and ‘doubleBookedEvents’ that will store the interval of the events that are caused at least once and the events that cause conflict exactly two times.
- For processing an event,
- First, iterate over the ‘doubleBookedEvents’ array and check for conflict. If it exists then return ‘False’ because it will cause triple booking.
- Then iterate over the ‘Events’ array and check for conflict. If it exists then add the event with the conflict to the ‘doubleBookedEvents’ array because it causes conflict exactly two times.
- Then add this event to the ‘Event’ array.
- And return ‘True’.
- The idea behind this approach is that we will maintain a HashMap in which:
- We will store the timestamp for each unit of time. Initially, all the timestamps will be 0. In the case of 'Start' time, we will increase its timestamp by 1. In the case of 'End' time, we will decrease its timestamp by 1.
- Consider a case when we only have one ‘Start' and one 'End' time, then the sum between them will be 0, so it will balance out. Now, if we add an overlap between the 'Start/End' time we will have the following:
- s0, s1, e0, e1 then the sum will be 1 2 1 0.
- Since there is an overlap, we can see that our highest sum is equal to 2.
- We can extend this approach for 3 or more overlaps.
- Example: s0, s1, s2, e0, e1, e3 then the sum will be 1 2 3 2 1 0. In this case, our sum has reached 3 and we have found a triple booking.
Algorithm:
- Create a HashMap ‘timeStamp’.
- For each of the events,
- Increase timeStamp[Start] by 1 and decrease timeStamp[End] by 1.
- Define the variable ‘Sum’ to store the sum of time stamps. Initialize it as 0.
- Now iterate over the map and find the sum of the values of the keys. While adding the timestamps from left to right, if the variable 'Sum' becomes greater than or equal to 3, then we will decrease timeStamp[Start] by 1 and increase timeStamp[End] by 1, in order to remove the added event and we will return ‘False’ because this means that it causes triple booking.
- Otherwise, we will return ‘True'.