One-Row Lecture Hall Problem

Prompt

A lecture hall has one row of seats, and people may enter from either the left end or the right end. Some seats are already occupied, every person has weight either 1 or 2, and exactly one new person will arrive for each empty seat in a fixed order. For each arriving person, you choose which end they enter from and which currently empty seat they take. To reach that seat, they must pass every occupied person between the chosen entrance and the seat, and passing a person causes inconvenience equal to (arriving person’s weight) * (seated person’s weight). After sitting down, the arriving person becomes occupied and may be passed by later people. For example, if the initial row is [empty, 1, empty, 1, 2] and the arrival order is [2, 1], one valid plan is to have the weight-2 person enter from the left and take the first seat for cost 0, then have the weight-1 person enter from the right and take the remaining seat, passing people of weights 2 and 1 for cost 1*2 + 1*1 = 3, for a total cost of 3. Given the initial row and the arrival order, either give a polynomial-time algorithm that finds the minimum possible total inconvenience, or prove that the problem is NP-hard.