Программа C++ для задачи распределения шоколада

Дан массив из n целых чисел, где каждое значение представляет количество конфет в пачке. В каждой пачке может быть разное количество конфет. Есть m учеников, задача состоит в том, чтобы распределить шоколадные пакеты так, чтобы:

1. Каждый ученик получает один пакет.
2. Разница между количеством шоколадок в пачке с максимальным количеством конфет и в пачке с наименьшим количеством шоколадок, выдаваемых учащимся, минимальна.

Примеры:

Input : arr[] = {7, 3, 2, 4, 9, 12, 56} , m = 3 
Output: Minimum Difference is 2 
Explanation:
We have seven packets of chocolates and 
we need to pick three packets for 3 students 
If we pick 2, 3 and 4, we get the minimum 
difference between maximum and minimum packet 
sizes.

Input : arr[] = {3, 4, 1, 9, 56, 7, 9, 12} , m = 5 
Output: Minimum Difference is 6 
Explanation:
The set goes like 3,4,7,9,9 and the output 
is 9-3 = 6

Input : arr[] = {12, 4, 7, 9, 2, 23, 25, 41, 
30, 40, 28, 42, 30, 44, 48, 
43, 50} , m = 7 
Output: Minimum Difference is 10 
Explanation:
We need to pick 7 packets. We pick 40, 41, 
42, 44, 48, 43 and 50 to minimize difference 
between maximum and minimum. 

Источник: Опыт интервью Flipkart.

Простое решение состоит в том, чтобы сгенерировать все подмножества размера m из arr[0..n-1]. Для каждого подмножества найти разницу между максимальным и минимальным элементами в нем. Наконец, верните минимальную разницу.
Эффективное решение основано на наблюдении, что для минимизации разницы мы должны выбирать последовательные элементы из отсортированного пакета. Сначала мы сортируем массив arr[0..n-1], затем находим подмассив размера m с минимальной разницей между последним и первым элементами.

На изображении ниже показан пробный запуск описанного выше подхода:

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

Выход: Минимальная разница 10