(Java Code)

Millions of commercial airline flights cross the world's cities every year, and each one of these flights must solve what seems like a simple problem: how do you arrange where each passenger on one of those flights sits? In this assignment, we will solve a variation on that problem, where we will observe one restriction on the seats: people who book a flight together will be if possible seated together.

Your program will process data from an array of strings (call this the "bookings" array). The first array element will contain a number indicating how many seats the aircraft has. The remaining elements will contain information about groups of passengers who have booked seats on the flight. The first element of this grouping will be a number that indicates how many people are in the group. The remaining elements identify the individual passengers in that group by their last and first name. For example, the array might contain the following 10 strings:

8 2 Nobbly, Greg Nobbly, Jo-Anne 1 Lee, Sook 3 Lukas, Stephie Lukas, Cambridge Lukas, Ogden 

which means there are 8 seats on the flight, the first group of passengers has 2 people (with their names below), the second group has 1 person, and the third group has 3 people.

Normally this data would come from input, such as lines from a text file, not from an array. That's the next assignment.

The seating chart for the flight will be stored in an array of strings (call this the "seats" array), whose size is equal to the number of seats on the flight. Each position in the array corresponds to a seat on the flight; the first element in the array is seat 1, the second element is seat 2, etc. Initially all the seats are empty. Passengers will be seated by placing their name in this array.

Your program will seat passengers as follows:

It will create a "seats" array of the appropriate size (given in the first position of the "bookings" array).

It will process the remaining items in the "bookings" array of strings. For each group of passengers it will attempt to seat them as follows:

First, it will see if there are enough seats remaining on the flight for everyone in the group; if not, it will display an error message and not assign seats to anyone in the group.

Secondly, it will go through the "seats" array to determine if a block of empty seats large enough to seat the entire group together is available (for example, if the group size is 3, it will see if there are 3 consecutive empty seats).

If there is at least one such block of seats anywhere in the array, randomly assign the group to one of these blocks by randomly selecting an element in the "seats" array. If that seat is empty, determine if enough successive array elements (seats) are also empty to seat the entire group; if so, seat them there. Otherwise, randomly try another seat, repeating until successful. (Note that this is not the most efficient approach...)

If there is no such block, randomly assign each passenger in the group individually to a seat (i.e., the group will be split up). For each passenger, pick random seat numbers until you find an empty seat.

When the seats for the flight have been assigned, print the contents of the "seats" array (neatly) to the display. Show both filled and empty seats, describing empty seats as "empty" (do not display the word "null"). Label each line of output with the seat number, where the first seat on the aircraft is seat 1.

Note that using the algorithm above, passengers never move once their seat has been assigned. A group may be split up due to the result of the randomly chosen seat locations. For example, the sample data above may result in the following output:

Seat 1: Lukas, Ogden Seat 2: Lee, Sook Seat 3: -empty- Seat 4: Lukas, Stephie Seat 5: Nobbly, Greg Seat 6: Nobbly, Jo-Anne Seat 7: -empty- Seat 8: Lukas, Cambridge 

Because the seat assignments for the first two groups left no block of three seats empty, each person in the third group had to each be assigned a random seat. If the first two groups had been seated differently, the third group may have been able to sit together.

Your main program will seat three flights. Each flight will be described by a "bookings" array that you will pass to a method that processes the array and determines the flight seating. Call the method three times in your main program, once for each "bookings" array. Display the seating plan for each flight under an appropriate title. Note that your main program should include only declarations, assignments, method calls, and output statements (no loops or other control structures); all the processing should be performed within other methods.

This is programming standard number 18, and should be followed in all your assignments, not just this one.

First, seat the flight containing the sample data shown above (eight seats, three groups). Next, create and seat your own booking array: give the flight 12 seats, and exactly five groups containing a total of 12 passengers. Make up the passenger names. Finally, download the class Bookings.class; inside is a method public static String[] getBookings()which will return an bookings array that you should seat.