Максимально увеличить число занятых ячеек в заданной матрице, удовлетворяющих условиям

Учитывая матрицу размерности N*M , задача состоит в том, чтобы максимизировать общее количество занятых ячеек в данной матрице так, чтобы они соответствовали заданному условию:

• Если две ячейки в одном ряду заняты, между ними должна быть хотя бы одна пустая ячейка.
• Если две ячейки заняты в разных рядах, между ними должен быть хотя бы один совершенно пустой ряд
  т. е. если клетки в i -й и j -й строке заняты так, что i < j , то должна быть k -я строка, полностью пустая, такая, что i < k < j .

Примеры:

Input: N = 1 ,M = 5
Output: 3
Explanation: There is only one row with five seats. 
Maximum three cells can be occupied. 
See the table below where 1 denotes occupied cell.

1

1

1

Input: N = 3 ,M = 3
Output: 4
Explanation:  There are three rows with three seats each.
Maximum occupied cells can be 4.

1		1
1		1

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

Ниже приведена реализация вышеуказанного подхода:

Сложность времени: О(Н*М)
Вспомогательное пространство: O(1), так как дополнительное пространство не занято.

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

So, the maximum number of cells that can be occupied for each row is ceil(M/2).
And as there is a gap of one row between any two occupied cells of different rows, 
the maximum number of rows that can be occupied is ceil(N/2).
Therefore maximum number of cells that can be occupied is ceil(M/2) * ceil(N/2).

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(1)
Вспомогательное пространство: O(1)