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.
Algorithm Requirements
The implementation must be able to accept any arbitrary amount of input and must be space and time efficient:
- 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
We will create a class Scheduler which holds a static method to determine the best time to schedule a meeting. The scheduleMeeting method will take in the number of time buckets the meeting should last and the schedules to check against. For 15 minute intervals, providing "4" for the value of time buckets will correspond to scheduling a meeting which is one hour long. In order to find an optimal time for the meeting, the scheduler will iterate through each time bucket, check how many schedules are open, and return immediately if an optimal solution is found: all schedules are open for the duration of the meeting, or the next best option if not: as many schedules as possible are open. For a single iteration, we will record the number of schedules which are open at that time bucket. We'll use a circular buffer to keep track of the numBuckets last counts. We'll also keep a sum value of the last numBucket counts. If that sum ever reaches numBuckets * numSchedules, we've found a perfect match and can return immediately. Otherwise, we'll return the highest value we've found. The full steps of the algorithm are:
- Create a circular buffer which will be used to keep track of the numBuckets most recent iterations.
- Initialize a sum numOpenSum to 0.
- Initialize bestOpenSum and bestOpenBucket to 0.
- Iterate over the first numBuckets buckets:
- Determine the number of schedules free at this bucket.
- Push that value to the circular buffer.
- Add that to numOpenSum
- Iterate from numBucket up to the last bucket:
- If numOpenSum is the ideal value, immediately return(i - numBuckets) * BUCKET_SIZE as the time to schedule the meeting.
- Otherwise, if numOpenSum > bestOpenSum, set the best sum and bucket to the numOpenSum and i - numBuckets.
- Dequeue from the circular buffer and subtract numOpenSum by that value.
- Determine the number of schedules free at this bucket.
- Push that value to the circular buffer.
- Add that to numOpenSum
- Perform a last check to see if the very last iteration has produced the optimal value.
- Return bestOpenBucket.
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.
Complexity | Notes | |
---|---|---|
Space | O(k) | 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 | O(n * b) | 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). |