My Calendar
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

Question

My Calendar

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

Accepted Answer

Brute Force Approach

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’.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of events.

O(N) space is required to store the events in the ‘Events’ array and the events that are conflicting twice in the ‘doubleBookedEvents’ array.

Hence, the overall Space Complexity is O(N).

Time Complexity: O(n^2)Explanation:

O(N ^ 2), where ‘N’ is the total number of events.

We are iterating over the ‘doubleBookedEvents’ and the ‘Events’ array which will take O(N) time for each one of the ‘N’ events. Hence, the overall total Time Complexity is O(N ^ 2).

Java (SE 1.8)

/*

    Time complexity : O(N^2)

    Space Complexity: O(N)



    Where 'N' is the number of events

*/



import java.util.ArrayList;



public class MyCalendar

{

    // It will store all the events that occur atleast once

    ArrayList> events;



    // It will store all the events that occur exactly two times

    ArrayList> doubleBookedEvents;



    public MyCalendar()

    {

        events = new ArrayList>();

        doubleBookedEvents = new ArrayList>();

    }



    public boolean book(int start, int end)

    {

        // Check for triple booking

        for (int i = 0; i < doubleBookedEvents.size(); i++)

        {

            if (doubleBookedEvents.get(i).get(0) < end && doubleBookedEvents.get(i).get(1) > start)

            {

                return false;

            }

        }



        // Check for double booking

        for (int i = 0; i < events.size(); i++)

        {

            if (events.get(i).get(0) < end && events.get(i).get(1) > start)

            {

                ArrayList temp = new ArrayList();

                temp.add(Math.max(events.get(i).get(0), start));

                temp.add(Math.min(events.get(i).get(1), end));



                doubleBookedEvents.add(new ArrayList(temp));

            }

        }



        // Add new event

        ArrayList temp = new ArrayList();

        temp.add(start);

        temp.add(end);



        events.add(new ArrayList (temp));

        return true;

    }

}

C++ (g++ 5.4)

/*

    Time complexity: O(N^2)

    Space Complexity: O(N)



    Where N is the number of events

*/



class MyCalendar 

{

    public:

	

    // It will store all the events that occur atleast once

    vector> events;



    // It will store all the events that occur exactly two times

    vector> doubleBookedEvents;



    bool book(int start , int end) 

    {



		// Check for triple booking

		for (int i = 0 ; i < doubleBookedEvents.size() ; i++) 

		{

			if (doubleBookedEvents[i][0] < end && doubleBookedEvents[i][1] > start) 

			{

				return false;

			}

        }



		// Check for double booking

		for (int i = 0 ; i < events.size() ; i++) 

		{

			if (events[i][0] < end && events[i][1] > start) 

			{

				doubleBookedEvents.push_back({max(events[i][0] , start) , min(events[i][1] , end)});

			}

		}



		// Add new event

		events.push_back({start , end});

		return true;

    }

};

Python (3.5)

'''

    Time complexity: O(N^2)

    Space Complexity: O(N)



    Where N is the number of events

'''



class MyCalendar:



    def __init__(self):



        # It will store all the events that occur atleast once

        self.events = []



        # It will store all the events that occur exactly two times

        self.doubleBookedEvents = []



    def book(self, start, end):



        # Check for triple booking

        for i in range(len(self.doubleBookedEvents)):



            if (self.doubleBookedEvents[i][0] < end and self.doubleBookedEvents[i][1] > start):

                return False



        # Check for double booking

        for i in range(len(self.events)):

            

            if (self.events[i][0] < end and self.events[i][1] > start):

                self.doubleBookedEvents.append([max(self.events[i][0], start),

                        min(self.events[i][1], end)])



        # Add new event

        self.events.append([start, end])

        return True

Accepted Answer

Solution using HashMap

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'.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of events.

O(N) space is required to store the events in the map ‘timeStamp’. Hence, the overall Space Complexity is O(N).

Time Complexity: O(n^2)Explanation:

O(N ^ 2), where ‘N’ is the total number of events.

Since there are ‘N’ events and for each of these events, and inserting each event in HashMap will take O(log(N)) time. We are iterating over the ‘timeStamp’ HashMap which will take O(N) time per event.

Hence, the overall Time Complexity is O(N ^ 2).