Arrange n items in k nonempty groups such that the difference between the minimum element and the maximum element of each group is minimized

Question

Given N items with values x[1], ..., x[n] and an integer K find a linear time algorithm to arrange these N items in K non empty groups such that in each group the range (difference between minimum and maximum element values/keys in each group) is minimized and therefore the sum of the ranges is minimum.

For example given N=4, K=2 and the elements 1 1 4 3 the minimum range is 1 for groups (1,1) and (4,3).

Answer 1

You can binary search the answer.
Assume the optimal answer is x. Now you should verify whether we can group the items into k groups where the maximum difference between the group items is at most x. This can be done in O(n) [after sorting the array]. Traverse the sorted array and pick consecutive items until the difference between minimum number you have picked for this group and the maximum number you have picked hasn't exceeded x. After that you should initialize a new group and repeat this process. At the end count how many groups you have made. If the number of groups is more than k we can conclude that we can not group the items in k groups with x being the answer. So we should increase x. By binary searching on x we can find the minimum x.

The overall complexity is O(NlogN).

Here is a sample implementation in C++

#include <algorithm>
#include <iostream>

using namespace std;

int main()
{
    int n = 4, k = 2;
    std::vector<int> v = {1, 1, 4, 3};
    sort(v.begin(), v.end());

    int low = 0, high = *max_element(v.begin(), v.end());

    while ( low < high ){
        int x = (low+high)/2;

        int groups = 0;
        int left = 0;
        while (left < v.size()){
            int right = left;
            while( right < v.size() && v[right] - v[left] <= x ){
                ++right;
            }
            ++groups;
            left = right;
        }
        // printf("x:%d groups:%d\n", x, groups );
        if (groups > k)
        {
            low = x + 1;
        } else {
            high = x;
        }
    }

    cout << "result is " << low << endl;

}