FAANG SWE算法面试题：影院不相邻座位安排判定实现

问题说明 #

这是一道FAANG软件工程师（SWE）算法与数据结构方向的编程面试题，核心需求是实现判定函数seatingProgram(seats, numToBeSeated)，返回布尔值True/False，代表待安排观影团是否满足就座条件。

题目规则 #

• 输入参数seats为仅包含0、1的一维数组：1代表对应位置座位已被占用，0代表对应位置为空座
• 入座唯一约束：所有新安排的观众不得与任何人（原已就座人员、其他新安排人员）相邻就座
• 输入参数numToBeSeated为大于0的正整数，代表待安排观影团的总人数

测试示例 #

• 输入seats = [1,0,0,0,0,0,1,0,0]：numToBeSeated=3时返回True（最优入座后数组为[1,0,1,0,1,0,1,0,1]），numToBeSeated=4时返回False
• 输入seats = [0]，numToBeSeated=1时返回True
• 输入seats = [1]，numToBeSeated=1时返回False
• 输入seats = [0,0]：numToBeSeated=1时返回True，numToBeSeated=2时返回False

实现思路 #

最优解法选择贪心策略即可，时间复杂度O(n)，空间复杂度可做到O(1)，效率高于动态规划方案：
从左到右遍历所有座位，只要当前位置为空，且左右直接相邻的位置都没有被占用（边界位置仅需判断存在的一侧），就直接安排观众入座，计数累加，同时跳过下一个相邻位置（避免重复判断相邻空位），计数达到待安排人数时直接提前返回True，遍历结束后比较计数和待安排人数即可。
贪心策略的正确性保证：对于每一个可入座的空位，优先选择最左侧位置入座，可安排的总人数不会少于选择右侧位置的方案，不会丢失最优解。

如果需要动态规划实现思路也可参考：定义dp[i]为前i个座位最多可安排的观众数，若第i位可入座则dp[i] = dp[i-2] + 1，不可入座则dp[i] = dp[i-1]，最终比较dp末尾值和待安排人数即可，该方案时间复杂度同样为O(n)，但实际运行常数开销高于贪心实现。

Python代码实现 #

不修改原输入数组版本（推荐） #

def seatingProgram(seats: list[int], numToBeSeated: int) -> bool:
    seat_count = len(seats)
    arranged = 0
    idx = 0
    while idx < seat_count:
        if seats[idx] == 0:
            # 判断左右相邻位置是否为空
            left_ok = (idx == 0) or (seats[idx-1] == 0)
            right_ok = (idx == seat_count - 1) or (seats[idx+1] == 0)
            if left_ok and right_ok:
                arranged += 1
                if arranged >= numToBeSeated:
                    return True
                # 当前位置已安排，相邻位置不可用，直接跳过下一个位置
                idx += 2
                continue
        idx += 1
    return arranged >= numToBeSeated

允许修改原数组的极简版本 #

def seatingProgram(seats: list[int], numToBeSeated: int) -> bool:
    n = len(seats)
    res = 0
    for i in range(n):
        if seats[i] == 0 and (i == 0 or seats[i-1] == 0) and (i == n-1 or seats[i+1] == 0):
            res += 1
            seats[i] = 1
            if res >= numToBeSeated:
                return True
    return res >= numToBeSeated

两个版本都通过了全部测试用例，支持提前终止遍历，在待安排人数较少时运行效率更高。

内容的提问来源于stack exchange，提问作者Alex