Lately, I took an interview. I was asked to design a meeting scheduler, just like in the Microsoft outlook calendar or the gmail calendar. I proposed that I will create an array of 48 for each day. Every 30 min representing the array entry.
I have to make sure that the next appointment does not collide with a previous meeting. My solution works fine but it wastes too much memory. Can anyone please tell me how do I find a better solution to detect collision for meetings. I don’t know all the meetings at the beginning. They will be added randomly later.
Approach: Using Array and Binary search
Start with an empty list of meetings, each with a start_time and duration. We will maintain a sorted list of meetings by start_time.
To add a meeting to the list, find where it belongs in the list by performing a binary search. Once you find the index, perform two checks to avoid a collision; consider the meetings immediately before and after the to-be-inserted meeting (if they exist).
Assert the before-meeting’s start_time + duration does not exceed the new meeting’s start_time.
Assert the new meeting’s start_time+duration does not exceed the after-meeting’s start_time.
If the assertions are satisfied, add the meeting to the list.
This add operation takes O(log(list_size)) time.
Note: This approach assumes that adding a meeting with an overlap is an invalid operation. If overlaps are allowed to exist, you would have to check beyond the meetings immediately preceding/subsequent the new meeting.
Approach 2: using BST
We can have a Tree structure (BST) for storing the requests (Request object: start time/end time/date/priority etc.). By doing so, add/delete/search/update operations can be achieved by O(height_of_tree). If we use a balanced tree, we can get the optimized running time. i.e. O(log n) for each of the above mentioned operations.
This approach is better than the sorted list approach as the list is backed by an fixed sized array in case of ArrayList which takes O(n) for copying the elements from old array to new array. If we use a linkedlist, binary search is not possible.