Бронирование мест в самолете

Вы обрабатываете бронирование мест в самолете. Есть N рядов, в кажом ряду 10 мест от A до K, при этом I пропущено, как на схеме:
  +---+---+---+  +---+---+---+---+  +---+---+---+ 
  | A | B | C |  | D | E | F | G |  | H | J | K |
  +---+---+---+  +---+---+---+---+  +---+---+---+ 
1 |   |   |   |  |   |   |   |   |  |   |   |   |
  +---+---+---+  +---+---+---+---+  +---+---+---+
2 |   |   |   |  |   |   |   |   |  |   |   |   |
  +---+---+---+  +---+---+---+---+  +---+---+---+
3 |   |   |   |  |   |   |   |   |  |   |   |   |
  +---+---+---+  +---+---+---+---+  +---+---+---+
   ... ... ...    ... ... ... ...    ... ... ...
   
  +---+---+---+  +---+---+---+---+  +---+---+---+
N |   |   |   |  |   |   |   |   |  |   |   |   |
  +---+---+---+  +---+---+---+---+  +---+---+---+
Некоторые из мест уже забронированы. Список забронированных мест даётся в виде строки, например: "1A 3C 2B 40G 5A".
Ваша задача забронировать места для семьи из 4 человек так, чтобы они были рядом. Места через проход, например, 2C и 2D - не рядом. Но семьи могут быть разделены проходом, если ровно по два человека из семьи сидят по разные стороны прохода.

Написать функцию:
func Solution(N int, S string) int
которая, при заданном числе рядов N и списке забронированных мест в виде строки S, возвращает, сколько максимум семтей из 4 человек могут быть рассажены по незабронированным местам .

Идея решения
Нам нужно знать, забронированы места B, C, D, E, F, G, H, J. И мы не рассматриваем места A и K.
[случай 1] Если B, C, D, E, F, G, H, J пусты, мы можем рассадить 2 семьи.
ИНАЧЕ
  • [случай 2] если B, C, D, E пусты - 1 семья
  • [случай 3] если D, E, F, G пусты - 1 семья
  • [случай 4] если F, G, H, J пусты - 1 семья.
Мы не можем рассадить больше семей сверх этой схемы.  И эта схема будет давать нам результат.

Компилируемое решение

public static int solve(int N, String s){    
    // исходная строка с забронированными местами, разделяем на массив
    String[] seats = s.split(" ");
    // карта забронированных мест
    boolean[][] map = new boolean[N][4];

    for(String seat : seats){
        // выделяем в каждой брони число и букву
        int num = Integer.parseInt(seat.substring(0, seat.length() - 1)) - 1;
        char c = seat.charAt(seat.length() - 1);


        if(c == 'B' || c == 'C'){
            map[num][0] = true; // пара BC занята в ряду num
        }else if(c == 'D' || c == 'E'){
            map[num][1] = true; // пара DE занята в ряду num
        }else if(c == 'F' || c == 'G'){
            map[num][2] = true; // пара FG занята в ряду num
        }else if(c == 'H' || c == 'J'){
            map[num][3] = true; // пара HJ занята в ряду num
        }
    }

    int ans = 0; // счётчик семей
    for(boolean[] row  : map){
        if(!row[0] && !row[1] && !row[2] && !row[3]){
            ans +=2; // случай 1 - 2 семьи
        }
        else{
            if(!row[0] && !row[1]){
                ans++; // случай 2 - 1 семья
            }
            else if(!row[1] && !row[2]){
                ans++; // случай 3 - 1 семья
            }
            else if(!row[2] && !row[3]){
                ans++; // случай 4 - 1 семья
            }
        }
    }
    return ans;
}

Комментарии

Популярные сообщения из этого блога

Разбиение числа на сумму с максимальным произведнием слагаемых

Число подмассивов, в которых сумма элементов равна k

Сложить два числа, которые представлены списком