Минимизировать затраты на уменьшение массива, если при выборе каждых 2 элементов 3-й выбирается бесплатно

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

Примеры:

Input: arr[] = {1, 2, 3}
Output: 5
Explanation: Choose 2 and 3, cost = 5. 1 is reduced from array for free.

Input: arr[] = {6, 5, 7, 9, 2, 2}
Output: 23

Подход: Эту проблему можно решить с помощью жадного подхода. Выполните следующие шаги, чтобы решить данную проблему.

• Отсортируйте заданный массив.
• Пройдите отсортированный массив с конца.
• Добавьте 2 элемента к конечной стоимости и пропустите 3-й.
• Верните окончательную стоимость.

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

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