A cinema row has seats numbered 0 to len(row) - 1. row[i] is 1 if seat i is taken and
0 if it is free. Then k strangers arrive one after another. Each stranger picks the free seat
whose distance to the nearest taken seat is as large as possible (the distance between seats
i and j is abs(i - j)). If several free seats tie, the stranger takes the one with the
smallest number. If the whole row is empty, the stranger takes seat 0. The chosen seat is then
taken for everyone who comes later. If the row is full, the remaining strangers leave.
Write cinema_seats(row, k) that returns the list of seats chosen, in order of arrival. Do not
change the input list.
Examples
Input: row = [1, 0, 0, 0, 0, 1, 0, 0], k = 3
Output: [2, 7, 1]
Explanation: seats 2 and 7 are both 2 away from anyone; 2 is smaller. Next, seat 7 is the only
seat 2 away. Then every free seat is 1 away, so seat 1 wins the tie.
Input: row = [0, 0, 0, 0], k = 5
Output: [0, 3, 1, 2]
Explanation: after four strangers the row is full, so the fifth leaves.
Input: row = [0, 1, 0], k = 1
Output: [0]
Constraints
0 <= len(row) <= 600,0 <= k <= 600
Goals
- Find the positions of the occupied seats and look at the gaps between them
- Treat the two ends of the row differently from the middle
- Apply a precise tie-break while scanning