My Calendar III

Easy
0/40
Average time to solve is 10m
profile
Contributed by
6 upvotes
Asked in companies
FacebookAmazon

Problem statement

A k-booking happens when k events have some non-empty intersection (i.e., there is some time that is common to all k events.) You are given some events [start, end), after each given event, return an integer k representing the maximum k-booking between all the previous events.

Implement the MyCalendarEvents class:

MyCalendarEvents() Initializes the object.

int book(int start, int end) Returns an integer k representing the largest integer such that there exists a k-booking in the calendar.

Note: 
Here the start of the event is included while the end is not as part of the slot i.e. the slot end right before the end.
For Example 
Input:
["MyCalendarEvents", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]  
Output:
[null, 1, 1, 2, 3, 3, 3]

Explanation:
MyCalendarEvents myCalendarEvent = new MyCalendarEvents();
myCalendarEvent.book(10, 20); // return 1, The first event can be booked and is disjoint, so the maximum k-booking is a 1-booking.
myCalendarEvent.book(50, 60); // return 1, The second event can be booked and is disjoint, so the maximum k-booking is a 1-booking.
myCalendarEvent.book(10, 40); // return 2, The third event [10, 40) intersects the first event, and the maximum k-booking is a 2-booking.
myCalendarEvent.book(5, 15); // return 3, The remaining events cause the maximum K-booking to be only a 3-booking.
myCalendarEvent.book(5, 10); // return 3
myCalendarEvent.book(25, 55); // return 3
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line determines the number of test cases that would be given in the problem.
The first line of each test case contains the integer ‘N’ which denotes the number of events that are going to be there.
Each ‘N’ line of input contains two space-separated integers where the first value is the start of the slot of the events ‘start’ while the second integer is the end of the slot of the events ‘end’.
Output Format: 
For every test case, return an integer k representing the maximum k-booking between all the previous events.

Print the output of each test case in a separate line.
Constraint : 
1 <= T <= 5
1 <= N <= 1000
0 <= start < end <= 10^9

Where ‘start’ is the start of the slot of the events ‘columns’ is the number of columns.

Time Limit: 1 sec
Sample Input 1:
2
3
1 2
1 2
2 3
2
10 20
15 30
Sample output 1:
1 2 2
1 2
Explanation:
For the first test case:

MyCalendarEvents myCalendarEvent = new MyCalendarEvents();
myCalendarEvent.book(1, 2); // return 1, The first event can be booked and is disjoint, so the maximum k-booking is a 1-booking.
myCalendarEvent.book(1, 2); // return 2, The second event [1, 2) intersects the first event, and the maximum k-booking is a 2-booking.
myCalendarEvent.book(2, 3); // return 2 

Hence the Output: [1,2,2]


For the second test case:

MyCalendarEvents myCalendarEvents = new MyCalendarEvents();
myCalendarEvent.book(10, 20); // return 1, The first event can be booked and is disjoint, so the maximum k-booking is a 1-booking.
myCalendarEvent.book(15, 30); // return 2, The second event [1, 2) intersects the first event, and the maximum k-booking is a 2-booking.


Hence the Output: [1,2]
Sample Input 2:
1
6
10 20
50 60
10 40
5 15
5 10
25 55
Sample output 2:
1 1 2 3 3 3
Hint

You can store the interval counts and find the maximum booked interval value for each given intersecting or non-intersecting sets of intervals.

Approaches (1)
Using Tree Map

The main idea here is to know that when booking a new event (start, end), we can count the timeSlot[start]++ and timeSlot[end]--. When processing the values of these time slots in the sorted order of their keys, the largest such value is the answer.

 

 

Algorithm:

 

  1. Initialise a dictionary/map/Tree Map for keeping track of the start and ends of the event intervals given.
  2. Now we keep adding the starts and ends of these events in our dictionary/map by increasing counts of the starts of the events by one each time a start of the event is encountered while we add the end of the interval and decrease its value by one.
  3. Now we sort the keys that we have in our dictionary/map and traverse the dictionary/map in sorted order and keep track of the largest value that we have for the set of event interval bookings that we have for various slots.
  4. We finally return the maximum k-booked event between all the previous events that we encountered.
Time Complexity

O(N ^ 2), where 'N' is the number of events booked. 
Leave a line blank line

Since, for each new event, we traverse the time slot in O(N) time. In Python, this is O(N ^ 2 * log (N)) owing to the extra sort step that we took.

Space Complexity

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

We are using a dictionary/map to store the event time slots hence, the Space Complexity is O( N ).

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