Finding Intervals | Rust

Write a function that takes in two array of time schedules, interval duration and returns the available common intervals of given duration.

We should find the interval of given duration in both schedules, we will have to iterate through both schedules, thus Time complexity will be O(Sh1 + Sh2), length of schedule1 + length of schedule2, Space complexity will also be O(Sh1 + Sh2).

Visualizing the common intervals for both schedules

We could add anything before start of the day and anything after end of the day as already scheduled to the array for both schedules, thus we don’t have perform any extra checks.

Now that we have all the information of already scheduled time, we don’t have to worry about daily bounds check, so we could merge both scheduled time arrays into one in increasing order. As our current updated arrays are already in increasing order of time, we can use to merge sort both arrays into one.

Now we have all the scheduled time in a single array, we can find the intervals that are common for both by combining all schedules into one as long as current schedule’s Start time is less than or equal to the previous schedule’s End time.

Flattening the Schedules into one

Now that we have the overall schedules, If the difference between two schedules is equal or greater than given meeting duration, then we have found a valid interval that is common between both schedules.

Finding Intervals

Code available here.

Helper Functions

We have two helper functions,

time_to_minutes takes time as time and returns the minutes, i.e “9:23” will be converted to 563 minutes as u32

minutes_to_time takes in minutes and returns the time in String, i.e 563 will be converted to “9:23” as String

This will help us to compare two time as integers and find if it is less or greater, later convert them back to String when needed.

Update Calendar with Starting and Ending Bounds as Schedules

update_calendar inserts “00:00” to Start_bounds to beginning of the array and pushes End_bounds to “23:59” to end of the array.

Merge Schedules with Merge Sort Method

We sort the array based on Starting time of every schedule in both array and return the merged array.

Flatten the Schedules

we create a new flattened array with first element in the merged array, we iterate from start of the second schedule in the merged array, and check if the previous schedule’s end time is less than or equal to the current schedule’s start time, if true we flatten that schedule by taking the start of previous schedule and max of (previous schedule’s end and current’s schedule’s end), and update the final element in the flattened array, else we push the current schedule to the end of the flattened array.

Finding Common Intervals

we iterate through the flattened array from the second element, if the difference between current element’s start and previous element’s end element is equal or greater than expected duration, then we update it to the intervals array.

Main Function

We will call the functions in this order: first we update the schedules, then we merge the schedules, then we flatten the schedules, finally we find the common intervals.

Result

Time complexity is O(sh1 + sh2), where sh1 is length of given calendar1 and sh2 is length of given calendar2.

Space complexity is O(sh1 + sh2), as we have to store the merged array which is will be of length sh1+sh2

Python Implementation here.