Минимизируйте расщепления в заданном массиве, чтобы найти подмножества не более чем из 2 элементов с суммой не более K

Учитывая массив arr[] из N целых чисел и целое число K , задача состоит в том, чтобы вычислить минимальное количество подмножеств почти из 2 элементов, которые можно разделить массив так, чтобы сумма элементов в каждом подмножестве была почти K .

Примеры:

Input: arr[] = {1, 2, 3}, K = 3
Output: 2
Explanation: The given array can be divided into subsets as {1, 2} and {3}, and the sum of both  the subsets is atmost K. Hence, the count of subsets is 2 which is the minimum possible.

Input: arr[] = {3, 2, 2, 3, 1}, K = 3
Output: 4

Input: arr[] = {3, 2, 2, 3, 1}, K = 2
Output: -1

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

• Отсортируйте заданный массив в порядке неубывания.
• Создайте две переменные, i = 0 и j = N – 1 , где i представляет первый индекс, а j представляет последний индекс массива.
• Если сумма arr[i] и arr[j] почти K , увеличьте i и уменьшите j. Кроме того, увеличьте счетчик подмножества на 1 .
• Если сумма arr[i] и arr[j] больше K , уменьшите j и увеличьте счетчик подмножества.

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

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