SmallOccupiedAirplane
SRM 816 · 2021-10-13 · by misof
Problem Statement
Your task is to write a function that will assign airplane seats to groups of passengers.
The airplane has R rows of seats. Rows are numbered from 1 (in the front) to R (in the back).
In each row there are six seats, labelled A, B, C, D, E, F. The label of each seat is its row followed by its letter. For example, the label of seat C in row 12 is the string "12C".
All seats can be ordered: first by row number and then by letter alphabetically. This will be called the canonical order. The first few seats in the canonical order: 1A, 1B, 1C, 1D, 1E, 1F, 2A, 2B, ...
In each row, seats A and F are called "window seats", seats C and D are called "aisle seats", and seats B and E are called "middle seats".
When seating the passengers, you must follow the following simple rules:
- Whenever you have multiple equally good options where to seat a passenger, choose the one among them that is first in the canonical order.
-
When seating a single passenger (a group of size 1):
- If there is an available window seat, give them a window seat. (The tiebreaker implies that you always choose the first available row, and within that row prefer seat A over seat F.)
- If there is an available aisle seat, give them an aisle seat. (Again, minimize row and prefer C over D.)
- And if there are only middle seats left, give them a middle seat.
-
When seating a group of passengers:
- If there are enough empty seats available in any row, seat all passengers in the group in the same row. (And, as the tiebreaker implies, use the first such row and within the row, use the leftmost seats available.)
- Otherwise, seat each member of the group as an individual passenger.
You are given the
Return a
Constraints
- R will be between 1 and 100, inclusive.
- Each element of groups will be between 1 and 6, inclusive.
- The sum of groups will not exceed 6*R.
1
{1, 1, 4}
Returns: {"1A", "1F", "1B", "1C", "1D", "1E" }
A single row of seats. The first passenger gets the seat 1A, the second passenger gets the seat 1F, and then the group of four gets the other four seats. Note that when assigning the seats to the four passengers, we do so in the canonical order: 1B, 1C, 1D, 1E.
10
{2, 1}
Returns: {"1A", "1B", "1F" }
The group of two passengers gets the seats 1A and 1B. Then, the single passenger gets the window seat 1F.
1
{1, 1, 1, 3}
Returns: {"1A", "1F", "1C", "1B", "1D", "1E" }
The first three passengers get seats 1A, 1F, and then 1C. The group of three then fills the remaining empty seats (from left to right).
2
{1, 1, 1, 5}
Returns: {"1A", "1F", "2A", "2B", "2C", "2D", "2E", "2F" }
Here, the first three passengers get seats 1A, 1F, and 2A. The group of five does not fit into row 1, so it goes into row 2.
2
{1, 1, 1, 1, 1, 5}
Returns: {"1A", "1F", "2A", "2F", "1C", "1D", "2C", "2D", "1B", "1E" }
The first four passengers grab the four window seats. The next passenger gets the aisle seat 1C. Finally, we have a group of five to seat. They don't fit into any row, so we handle them as five individual passengers. The first three of them grab the remaining aisle seats (in the order 1D, 2C, 2D), and the remaining two get the first two middle seats (1B, 1E). Note that in the return value the order of the last five seats is the order in which they were given to the individual members of the group of five.
3
{4, 4, 4, 1, 2, 1, 1, 1}
Returns: {"1A", "1B", "1C", "1D", "2A", "2B", "2C", "2D", "3A", "3B", "3C", "3D", "1F", "2E", "2F", "3F", "1E", "3E" }
The seats assigned to individual groups: {"1A", "1B", "1C", "1D", "2A", "2B", "2C", "2D", "3A", "3B", "3C", "3D", "1F", "2E", "2F", "3F", "1E", "3E" }
Submissions are judged against all 80 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class SmallOccupiedAirplane with a public method vector<string> seat(int R, vector<int> groups) · 80 test cases · 2 s / 256 MB per case