Maximum Consecutive Floors Without Special Floors

February 6, 2024

Problem Statement #

You are designing an algorithm for an elevator system in a skyscraper without accessing specific floors marked as special. Given a list of special floors specialFloors and two integers bottom and top indicating the lowest and highest floors you’re allowed to visit, return the maximum number of consecutive floors you can visit between bottom and top without stopping at any special floor. Special floors are guaranteed to be within the range of bottom to top.

Solution Approach #

The solution involves sorting the list of special floors and calculating the maximum gap between consecutive special floors, considering the bottom and top limits.

Algorithm Steps #

1. Sort the specialFloors list.
2. Initialize maxConsecutiveFloors to 0.
3. Add bottom-1 and top+1 as virtual special floors to handle edge cases.
4. Iterate through the sorted list of special floors to find the maximum gap between consecutive special floors.
5. Update maxConsecutiveFloors accordingly.
6. Return maxConsecutiveFloors as the answer.

Code (Python) #

def maxConsecutive(bottom, top, specialFloors):
    specialFloors.append(bottom - 1)
    specialFloors.append(top + 1)
    specialFloors.sort()

    maxConsecutiveFloors = 0
    for i in range(1, len(specialFloors)):
        # Calculate the gap between current and previous special floor, minus one to exclude the special floors themselves.
        maxConsecutiveFloors = max(maxConsecutiveFloors, specialFloors[i] - specialFloors[i-1] - 1)

    return maxConsecutiveFloors

# Example usage
print(maxConsecutive(1, 10, [4, 6]))  # Output: 4

Time Complexity #

• O(n log n) due to the sorting of special floors, where n is the number of special floors.

Space Complexity #

• O(1) if we ignore the input and output size, as we only use a fixed amount of extra space.