Как найти лучшее расположение сидений в театре для 2d массива

Question

Вы управляете небольшим театром, и каждый месяц у вас есть письма меценатов с просьбами о предварительной продаже билетов. Вам нужно обработать эти запросы на билеты и либо сообщить им, где будет сидеть их группа, либо объяснить покровителю, почему вы не можете выполнить их заказ.

У вас есть несколько правил, которым вы должны следовать при заполнении заказов:

1. Выполните как можно больше заказов
2. Разместите стороны как можно ближе к фронту.
3. Если в театре недостаточно мест для проведения вечеринки, скажите им: "Извините, мы не справимся с вашей вечеринкой".
4. Каждая партия должна сидеть в одном ряду в одном разделе. Если они не подходят, скажите им: "Позвоните, чтобы разделить партию".

Ваша программа должна проанализировать макет театра и список запросов на билеты и создать список билетов или объяснений в том же порядке, что и запросы.

Макет театра состоит из 1 или более рядов. Каждый ряд состоит из 1 или более разделов, разделенных пробелом.

После театрального макета есть одна пустая строка, за которой следует 1 или более театральных запросов. Театральный запрос состоит из имени, сопровождаемого пробелом и количеством запрошенных билетов.

Пример ввода:

6 6
3 5 5 3
4 6 6 4
2 8 8 2
6 6

Smith 2
Jones 5
Davis 6
Wilson 100
Johnson 3
Williams 4
Brown 8
Miller 12

Ваша программа должна выводить результаты для стандартного вывода в том же порядке, что и запросы, с указанием имени человека, который запросил билет, а также строки и раздела заявки или пояснений: "Извините, мы не можем справиться с вашей группой" или "Позвоните, чтобы разделить вечеринку".

Образец вывода:

`` `

Smith Row 1 Section 1
Jones Row 2 Section 2
Davis Row 1 Section 2
Wilson Sorry, we can't handle your party.
Johnson Row 2 Section 1
Williams Row 1 Section 1
Brown Row 4  Section 2
Miller Call to split party.

Answer 1

Возможно, вам следует записать то, что вы пробовали до сих пор. Во всяком случае, я думаю, что это можно решить с помощью следующего алгоритма. Вы можете написать то же самое.

1. Keep track of total_seats.

2. Sort the theater requests based on the number of seats needed (since filling more orders is the priority).

3. For each request :
       if request < total_seats :
           For each row:
               if request < seats_in_row:
                   total_seats -= seats
                   update theater_seat[row][column]
               else:
                  Call to split party. 

       else:
           Sorry, we can't handle your party.