A special theater has only one row of n seats. Any time a patron is brought to h

Question

A special theater has only one row of n seats. Any time a patron is brought to his or her assigned seat, any patrons already seated next to this seat must rise and sit again, as must any next to them, and so forth. For ex ample, if there are patrons in seats 1, 2, 4, and 6, and a new patron is to be brought to sit in seat 3, the patrons in seats 2 and 4 must rise and sit again, which in turn requires the patron in seat 1 to rise and sit again; so seating the new arrival in this case causes three additional reseatings.
As the owner of the theater, you would like to minimize the total number of seatings and reseatings necessary to seat the entire row of n patrons. Determine the order in which patrons should be brought to their seats so as to require only O(n log n) seatings and reseatings. Write a recurrence for the total number of (re)seatings and solve it. You may assume that n = 2k -1 for some integer k > 0. (Hint: Think about which seat should be saved for the last, and use recursion)

Explanation / Answer

Row consists of n seats.

Assume that n = 2k – 1, k0 that is n consists of odd number of seats. Consider the Patrons are in the form of A, B and C

Consider n = 3 seats

First Patrons should be filled at a corner that means it should be filled alternatively. From both sides to be filled at the middle in order to minimize the number of reseating.

n = 3 then

Thus the number of seating’s = 3 that is A, B, C, number of reseating’s = 2 by A and B

Consider n = 5 then the patrons be A ,B,C,D,E

From the above concept number of seating’s is 5 and number of reseating’s is 6

Minimize the number of reseating’s positions, and then alternatively arrange the patrons in both sides.

For n = 7 Patrons then

Minimize the number of reseating’s positions for A, B, C, D, E, F and G.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.