Разделить массив на минимальное количество подмножеств, имеющих разницу между максимальным и минимальным элементом не более K

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

Примеры:

Input: arr[] = {1, 2, 3, 4, 5}, K = 2 
Output: 2
Explanation:
The given array can be divided into two sets {1, 2, 3} having the difference between maximum and minimum as 3 – 1= 2 and {4, 5} having the difference between maximum and minimum as 5 – 4 = 1.

Input: arr[] = {5, 2, 9, 7, 3, 2, 4, 6, 14, 10}, K = 3
Output: 4

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

• Отсортируйте заданный массив arr[] в порядке неубывания.
• Инициализируйте два итератора begin и end как 0 , представляющие начало и конец каждого набора.
• Инициализируйте переменную, скажем, setCount как 1 , которая хранит результирующее минимальное количество разбиения элементов массива на подмассивы.
• Повторяйте цикл до тех пор, пока значение конца не станет меньше N , и выполните следующие шаги:
  1. Если значение arr[end] – arr[begin] <= K , то увеличьте значение end .
  2. В противном случае увеличьте значение setCount на 1 и обновите значение от начала до конца , представляющее новый набор.
• После выполнения вышеуказанных шагов выведите в качестве результата значение setCount .

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

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