In this article, we'll be taking a look at a possible interview question: design an algorithm that will take a list of schedules and a meeting duration and find an optimal time to schedule that meeting. First, we'll outline the requirements for the algorithm in terms of functionality and efficiency, then describe how we'll model the objects to be used, implement our solution, and finally, analyze the space and time complexity of the solution.
- The algorithm should be able to take any number of schedules and a meeting length and return a time such that the highest number of people can attend.
- The space complexity should be constant.
- The time complexity should be linear.
- It should not need to iterate through the possible times more than once.
Implementing the Schedule Object
We will create a class Schedule which will represent the schedule of a single person for a single day. The class will use 15 minute time buckets to record whether or not the schedule is open at each 15 minute interval of the day. We'll use a boolean array to store these values. The calendar will be open by default; a method will be available for the consumer to specify time ranges which should be marked as closed/unavailable. It will also be able to convert strings such as "8:30pm" to the array index of the corresponding bucket.
Creating the Scheduler
If there is a time where every schedule is open, this will return the first time bucket. Otherwise, it will return the time bucket where the most people can attend. This could be modified to return all times which are open, or all times which have the optimal solution if a perfect one does not exist.
Space and Time Complexity
In our analysis, we will refer to k as the number of buckets in the meeting we're trying to schedule, n as the number of schedules, and b as the number of time buckets in the day.
|Space||We are using k extra space in the circular buffer to record the last k iterations. If we consider this to be a constant factor, the space complexity wil be O(1).|
|Time||The algorithm will iterate over all buckets and access each schedule's bucket value. If we consider the buckets to be a constant factor, the time complexity will be O(n).|