When a group of people go to the cinema, they often want to sit together in the same row. When no such arrangements are available, they might not want to watch the movie anymore.

Hence, to keep more customers, the theater must have a wise seating plan. Here is a possible algorithm to make an arrangement for a group of \(n\) people:

Starting from the first row, find the leftmost \(n\) consecutive seats available, and place them there. If there are no such seats, move on to the next row, and repeat the procedure until the last row.

If no seats are found available in the cinema, they would have to reject the customers.

There are some cases where this algorithm doesn't distribute seats wisely. For a cinema with 2 rows, each row having 5 seats, which of the following cases could have a better arrangement if we had a different order of arrival?

For example, for a cinema with 2 rows with 5 seats in each, 4 groups of moviegoers--2, 4, 2, 5 people in each group--arriving in that order will be seated as follows:

  • Row 1 seats the first group of 2 in seat numbers 1-2.
  • Row 2 seats the second group of 4 in seat numbers 1-4.
  • Row 1 seats the third group of 2 in seat numbers 3-4.
  • Reject the fourth group.

Problem Loading...

Note Loading...

Set Loading...