3168. Minimum Number of Chairs in a Waiting Room

SourceWeekly Contest 400 Q1DifficultyEasyRating1211

Description

You are given a string s. Simulate events at each second i:

If s[i] == 'E', a person enters the waiting room and takes one of the chairs in it.
If s[i] == 'L', a person leaves the waiting room, freeing up a chair.

Return the minimum number of chairs needed so that a chair is available for every person who enters the waiting room given that it is initially empty.

Example 1:

Input: s = "EEEEEEE"

Output: 7

Explanation:

After each second, a person enters the waiting room and no person leaves it. Therefore, a minimum of 7 chairs is needed.

Example 2:

Input: s = "ELELEEL"

Output: 2

Explanation:

Let's consider that there are 2 chairs in the waiting room. The table below shows the state of the waiting room at each second.

Second	Event	People in the Waiting Room	Available Chairs
0	Enter	1	1
1	Leave	0	2
2	Enter	1	1
3	Leave	0	2
4	Enter	1	1
5	Enter	2	0
6	Leave	1	1

Example 3:

Input: s = "ELEELEELLL"

Output: 3

Explanation:

Let's consider that there are 3 chairs in the waiting room. The table below shows the state of the waiting room at each second.

Second	Event	People in the Waiting Room	Available Chairs
0	Enter	1	2
1	Leave	0	3
2	Enter	1	2
3	Enter	2	1
4	Leave	1	2
5	Enter	2	1
6	Enter	3	0
7	Leave	2	1
8	Leave	1	2
9	Leave	0	3

Constraints:

1 <= s.length <= 50
s consists only of the letters 'E' and 'L'.
s represents a valid sequence of entries and exits.

Solutions

Solution 1: Simulation

Thinking

E arrives and L leaves; chairs are bought only when none are free and never discarded. The peak occupancy is the answer.

A free chair is reused immediately: an arrival takes one if available, otherwise \(cnt\) grows; a leaving increments free chairs.

Track \(cnt\) and \(left\) across \(s\). The final \(cnt\) is the minimum number of chairs.

We use a variable cnt to record the current number of chairs needed, and a variable left to record the current number of remaining empty chairs. We traverse the string s. If the current character is 'E', then if there are remaining empty chairs, we directly use one empty chair, otherwise we need to add a chair; if the current character is 'L', then the number of remaining empty chairs increases by one.

After the traversal, we return cnt.

The time complexity is \(O(n)\), where \(n\) is the length of the string s. The space complexity is \(O(1)\).

Python3JavaC++GoTypeScript

class Solution:
    def minimumChairs(self, s: str) -> int:
        cnt = left = 0
        for c in s:
            if c == "E":
                if left:
                    left -= 1
                else:
                    cnt += 1
            else:
                left += 1
        return cnt

class Solution {
    public int minimumChairs(String s) {
        int cnt = 0, left = 0;
        for (int i = 0; i < s.length(); ++i) {
            if (s.charAt(i) == 'E') {
                if (left > 0) {
                    --left;
                } else {
                    ++cnt;
                }
            } else {
                ++left;
            }
        }
        return cnt;
    }
}

class Solution {
public:
    int minimumChairs(string s) {
        int cnt = 0, left = 0;
        for (char& c : s) {
            if (c == 'E') {
                if (left > 0) {
                    --left;
                } else {
                    ++cnt;
                }
            } else {
                ++left;
            }
        }
        return cnt;
    }
};

func minimumChairs(s string) int {
    cnt, left := 0, 0
    for _, c := range s {
        if c == 'E' {
            if left > 0 {
                left--
            } else {
                cnt++
            }
        } else {
            left++
        }
    }
    return cnt
}

function minimumChairs(s: string): number {
    let [cnt, left] = [0, 0];
    for (const c of s) {
        if (c === 'E') {
            if (left > 0) {
                --left;
            } else {
                ++cnt;
            }
        } else {
            ++left;
        }
    }
    return cnt;
}

3168. Minimum Number of Chairs in a Waiting Room

Description

Solutions

Solution 1: Simulation

Comments