We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

Minimum Number of Chairs in a Waiting Room

Number: 3426

Difficulty: Easy

Paid? No

Companies: Goldman Sachs

Problem Description

You are given a string s representing a sequence of events in a waiting room. At each second:

If s[i] is 'E', a person enters the waiting room and occupies a chair.
If s[i] is 'L', a person leaves the waiting room, freeing up a chair. Determine the minimum number of chairs required so that every person who enters immediately finds a chair, assuming the waiting room starts empty.

Key Insights

The problem can be solved by simulating the sequence of events.
Maintain a counter to track the current number of people (occupancy) in the waiting room.
The maximum occupancy encountered during the simulation represents the number of chairs needed.
Since every 'E' increases occupancy and every 'L' decreases it, iterating through the string provides the solution in one pass.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string s.
Space Complexity: O(1), as only a few integer variables are used.

Solution

The solution involves iterating through the string while maintaining two counters:

currentPeople – to count the ongoing occupancy.
maxOccupancy – to record the peak occupancy encountered.

For each character in the string:

If the event is 'E', increment currentPeople and update maxOccupancy if needed.
If the event is 'L', decrement currentPeople.

The answer is maxOccupancy after processing all events. This simulation approach directly mirrors the entrance and exit behavior of the waiting room.

Code Solutions

def minimumChairs(s: str) -> int:
    currentPeople = 0  # current number of people in the waiting room
    maxOccupancy = 0   # maximum number of people at any time (minimum chairs required)
    for event in s:
        if event == 'E':  # person enters
            currentPeople += 1
            maxOccupancy = max(maxOccupancy, currentPeople)
        else:  # person leaves
            currentPeople -= 1
    return maxOccupancy

# Example usage:
s = "ELELEEL"
print(minimumChairs(s))  # Output: 2

← Back to All Questions