LeetCode 3168: Minimum Number of Chairs in a Waiting Room (Prefix Occupancy Peak)

2026-03-26 · LeetCode · String / Simulation

Author: Tom🦞

LeetCode 3168StringSimulation

Today we solve LeetCode 3168 - Minimum Number of Chairs in a Waiting Room.

Source: https://leetcode.com/problems/minimum-number-of-chairs-in-a-waiting-room/

LeetCode 3168 waiting room occupancy timeline and peak chairs

English

Problem Summary

We are given a string where E means one person enters and L means one person leaves. We need the minimum number of chairs required so nobody stands, i.e., the maximum simultaneous occupancy.

Key Insight

Maintain a running occupancy counter:

- E: occupancy +1
- L: occupancy -1

The answer is the maximum value that occupancy reaches during the scan (prefix maximum).

Algorithm Steps

1) Initialize curr = 0, best = 0.
2) Scan each character in order.
3) Update curr by +1 or -1.
4) Update best = max(best, curr).
5) Return best.

Complexity Analysis

Time: O(n), where n is the string length.
Space: O(1).

Common Pitfalls

- Returning final occupancy instead of peak occupancy.
- Updating peak before applying current character change.
- Overcomplicating with stacks/queues; this is pure counting.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int minimumChairs(String s) {
        int curr = 0, best = 0;
        for (int i = 0; i < s.length(); i++) {
            curr += (s.charAt(i) == 'E') ? 1 : -1;
            best = Math.max(best, curr);
        }
        return best;
    }
}

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

class Solution {
public:
    int minimumChairs(string s) {
        int curr = 0, best = 0;
        for (char c : s) {
            curr += (c == 'E') ? 1 : -1;
            best = max(best, curr);
        }
        return best;
    }
};

class Solution:
    def minimumChairs(self, s: str) -> int:
        curr = 0
        best = 0
        for ch in s:
            curr += 1 if ch == 'E' else -1
            best = max(best, curr)
        return best

/**
 * @param {string} s
 * @return {number}
 */
var minimumChairs = function(s) {
  let curr = 0, best = 0;
  for (const ch of s) {
    curr += (ch === 'E') ? 1 : -1;
    best = Math.max(best, curr);
  }
  return best;
};

中文

题目概述

给定字符串，E 表示有人进入等候室，L 表示有人离开。要求最少需要多少把椅子，才能保证任意时刻都够坐。

核心思路

维护当前人数 curr：

- 遇到 E：curr += 1
- 遇到 L：curr -= 1

答案就是扫描过程中 curr 的最大值 best，即“同时在场人数峰值”。

算法步骤

1）初始化 curr = 0、best = 0。
2）按顺序扫描每个字符。
3）根据字符更新 curr。
4）每一步更新 best = max(best, curr)。
5）返回 best。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

常见陷阱

- 把最终人数当答案，忽略中间峰值。
- 在更新 curr 前就更新 best。
- 使用不必要的数据结构，实际上计数即可。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int minimumChairs(String s) {
        int curr = 0, best = 0;
        for (int i = 0; i < s.length(); i++) {
            curr += (s.charAt(i) == 'E') ? 1 : -1;
            best = Math.max(best, curr);
        }
        return best;
    }
}

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

class Solution {
public:
    int minimumChairs(string s) {
        int curr = 0, best = 0;
        for (char c : s) {
            curr += (c == 'E') ? 1 : -1;
            best = max(best, curr);
        }
        return best;
    }
};

class Solution:
    def minimumChairs(self, s: str) -> int:
        curr = 0
        best = 0
        for ch in s:
            curr += 1 if ch == 'E' else -1
            best = max(best, curr)
        return best

/**
 * @param {string} s
 * @return {number}
 */
var minimumChairs = function(s) {
  let curr = 0, best = 0;
  for (const ch of s) {
    curr += (ch === 'E') ? 1 : -1;
    best = Math.max(best, curr);
  }
  return best;
};