Programa C++ para el problema de distribución de chocolate

Dada una array de n enteros donde cada valor representa la cantidad de chocolates en un paquete. Cada paquete puede tener un número variable de bombones. Hay m estudiantes, la tarea es distribuir paquetes de chocolate de tal manera que: 

1. Cada estudiante recibe un paquete.
2. La diferencia entre la cantidad de chocolates en el paquete con el máximo de chocolates y el paquete con el mínimo de chocolates que se les da a los estudiantes es mínima.

Ejemplos:

Entrada: arr[] = {7, 3, 2, 4, 9, 12, 56} , m = 3 
Salida: La diferencia mínima es 2 
Explicación:
Tenemos siete paquetes de chocolates y 
necesitamos elegir tres paquetes para 3 estudiantes 
Si elegimos 2, 3 y 4, obtenemos la diferencia mínima  entre los tamaños
de paquete máximo y mínimo  .

Entrada: arr[] = {3, 4, 1, 9, 56, 7, 9, 12}, m = 5 
Salida: La diferencia mínima es 6 
Explicación:
El conjunto va como 3,4,7,9,9 y el la salida 
es 9-3 = 6

Entrada: arr[] = {12, 4, 7, 9, 2, 23, 25, 41, 
30, 40, 28, 42, 30, 44, 48, 
43, 50}, m = 7 
Salida: La diferencia mínima es 10 
Explicación:
Necesitamos recoger 7 paquetes. Elegimos 40, 41, 
42, 44, 48, 43 y 50 para minimizar la diferencia 
entre el máximo y el mínimo. 

Fuente: Experiencia de entrevista Flipkart

Una solución simple es generar todos los subconjuntos de tamaño m de arr[0..n-1]. Para cada subconjunto, encuentre la diferencia entre los elementos máximo y mínimo en él. Finalmente, devuelva la diferencia mínima.
Una solución eficiente se basa en la observación de que para minimizar la diferencia, debemos elegir elementos consecutivos de un paquete ordenado. Primero ordenamos el arreglo arr[0..n-1], luego encontramos el subarreglo de tamaño m con la diferencia mínima entre el último y el primer elemento.

La imagen de abajo es una ejecución en seco del enfoque anterior:

A continuación se muestra la implementación del enfoque anterior: 

// C++ program to solve chocolate 
// distribution problem
#include <bits/stdc++.h>
using namespace std;
  
// arr[0..n-1] represents sizes of packets
// m is number of students.
// Returns minimum difference between maximum
// and minimum values of distribution.
int findMinDiff(int arr[], int n, int m)
{
    // If there are no chocolates or number
    // of students is 0
    if (m == 0 || n == 0)
        return 0;
  
    // Sort the given packets
    sort(arr, arr + n);
  
    // Number of students cannot be more than
    // number of packets
    if (n < m)
        return -1;
  
    // Largest number of chocolates
    int min_diff = INT_MAX;
  
    // Find the subarray of size m such that
    // difference between last (maximum in case
    // of sorted) and first (minimum in case of
    // sorted) elements of subarray is minimum.
  
    for (int i = 0; i + m - 1 < n; i++) 
    {
        int diff = arr[i + m - 1] - arr[i];
        if (diff < min_diff)
            min_diff = diff;
    }
    return min_diff;
}
  
// Driver code
int main()
{
    int arr[] = {12, 4,  7,  9,  2,  23, 25, 
                 41, 30, 40, 28, 42, 30, 44, 
                 48, 43, 50 };
  
    // Number of students
    int m = 7; 
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Minimum difference is " << 
             findMinDiff(arr, n, m);
    return 0;
}

Salida: La diferencia mínima es 10