Chương trình Python kiểm tra xem tất cả mọi người có thể ngồi được không

Giả sử chúng ta có một số n đại diện cho số người đang tìm chỗ ngồi, và một danh sách các bit trong đó 1 biểu thị ghế đã có người ngồi, 0 biểu thị ghế trống. Không có hai người nào được ngồi cạnh nhau. Ta cần kiểm tra xem tất cả n người có thể tìm được chỗ ngồi hay không.

Ví dụ: với n = 2 và seats = [1, 0, 0, 0, 1, 0, 0], kết quả là True vì họ có thể ngồi tại chỉ số 2 và 6.

Thuật toán

1. Thêm 0 vào đầu mảng seats và thêm [0, 1] vào cuối.
2. Khởi tạo res = 0 (số chỗ ngồi khả dụng) và gap = 0 (độ dài đoạn ghế trống liên tiếp).
3. Duyệt qua từng phần tử i trong mảng seats:
   • Nếu i == 0: tăng gap lên 1.
   • Ngược lại, nếu gap > 0:
     • Cộng vào res giá trị (gap - 1) // 2 (số người tối đa có thể ngồi trong đoạn trống đó).
     • Đặt lại gap = 0.
4. Trả về True nếu res >= n, ngược lại False.

Mã Python

def solve(n, seats):
    seats = [0] + seats + [0, 1]
    res = 0
    gap = 0
    for i in seats:
        if i == 0:
            gap += 1
        elif gap > 0:
            res += (gap - 1) // 2
            gap = 0
    return res >= n

n = 2
seats = [1, 0, 0, 0, 1, 0, 0]
print(solve(n, seats))  # True

Đầu vào / Đầu ra

Input: 2, [1, 0, 0, 0, 1, 0, 0]

Output: True