My Calendar

Easy
0/40
Average time to solve is 15m
profile
Contributed by
4 upvotes
Asked in companies
AmazonMicrosoftThought Works

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
6
10 20
50 60
10 40
5 15
5 10
25 55
4
1 10
20 30
5 6
8 9
Sample Output 1:
True True True False True True
True True True True
Explanation For Sample Input 1:
For the first test case, 

The first two events can be booked. The third event can be booked because it causes conflict with the first event only once.The fourth event (5, 15) can't be booked, because it would result in a triple booking. The fifth event (5, 10) can be booked, as it does not use time [1, 10) or overlapping instead it overlaps with [5, 15) which is overlapped once. The sixth event (25, 55) can be booked, as it will overlap with the third event with the time [10, 40) which is also overlapped only once.

For the second test case,

The first two events can be booked. The third event will also be booked as it will be overlap with the first event. The fourth event will be booked because it will overlap with the first event only and not with the third event.
Sample Input 2:
2
4
1 10
20 30
5 6
2 7
5
1 10
20 30
1 15
8 9 
10 15
Sample Output 2:
True True True False
True True True False True
Hint

In the calendar, there will be only two types of events one that occurs at least one time and the other that occurs exactly two times?

Approaches (2)
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’.
Time Complexity

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

Space Complexity

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

Code Solution
(100% EXP penalty)
My Calendar
Full screen
Console