Find the longest consecutive busy period of an employee’s outlook calendar..

Photo by Scott Rodgerson on Unsplash

A person has divided their workday into 15-minute time slots numbered as 1, 2, 3, ... n. People who want to schedule a meeting with this person choose any available time slot that suits them. Assume that this person’s calendar is now filled with jumbled-up numbers that represent the time slots reserved for meetings. Your task is to find out what the longest consecutive time period in which this person will be busy is.

The following illustration shows how we will be mapping the 15-minute time slots to the numbers given in the input:

For example, you are given the following list of busy slots: [3, 1, 15, 5, 2, 12, 10, 4, 8, 9]. In this list, the longest sequence of consecutive slots is [1, 2, 3, 4, 5]. Since the length of this sequence is five, your function should return 5.

Solution

The longest busy period can start from any of the array’s indexes, so we have to search the entire array. Additionally, for each slot, we need to look up the entire array for the next consecutive slot. We can use the HashSet data structure and convert a linear time lookup to constant time to find the longest sequence of consecutive numbers.

Here is how the implementation will take place:

1. Initialize a HashSet data structure and store the busy schedule in it.
2. Traverse the input array, and for each time slot, check if the next consecutive slot is in the array or not.
3. If the above condition is true, keep incrementing the slot number until we get a slot that is not in the set.
4. We will keep the count of consecutive slots in a variable. If the current longest slot count is greater than the previously calculated one, we will replace it with the current one.
5. Return the largest slot count at the end.

Time complexity

The time complexity will be O(n), where n is the size of the input array. The time complexity might appear quadratic because of the while loop inside the for loop. However, upon closer inspection, we can see that it will be linear. This is because the while loop is reached only when currentSlot is at the beginning of a sequence (meaning currentSlot-1 is not present in schedule), and the while loop can only run for n iterations throughout the entire algorithm. This means that, even though it seems like O(n×n) complexity, the nested loops actually run in O(n+n) = O(n) time.

Space complexity

The space complexity will be O(n) because we use the hash set to store n slots.