What about the greedy approach, i.e. insert elements from the left into a set, when you go over the desired difference, create a new set.
So, for 1, 2, 3, 7, 8, 9, 11, 15, 16
:
You'd start off with 1.
2-1 = 1 < 9, so add 2.
3-1 = 2 < 9, so add 3.
7-1 = 6 < 9, so add 7.
8-1 = 7 < 9, so add 8.
9-1 = 8 < 9, so add 9.
11-1 = 10 > 9, so create a new set.
15-11 = 4 < 9, so add 15.
16-11 = 5 < 9, so add 16.
Output: {1, 2, 3, 7, 8, 9}, {11, 15, 16}
.
Note:
If the elements aren't necessarily ordered, we can simply sort them first.
If these subsets don't have to be continuous, it doesn't make a difference, as selecting continuous sets from the ordered input is always better than non-continuous sets.
If the elements aren't necessarily ordered and the subsets must be continuous, that will change the problem a bit.
Proof of optimality:
Let S be the set assignment produced by this algorithm for some arbitrary input.
Take any set assignment T.
Let Si be the i-th set of S.
Let Ti be the i-th set of T.
Let Si-size be the size of the i-th set of S.
Let Ti-size be the size of the i-th set of T.
Assume S and T are different, then for some Si and Ti, Si-size != Ti-size. Specifically choose the first set i
where the two differ.
So either Si-size > Ti-size or Si-size < Ti-size.
j > i is impossible, since this algorithm takes as many elements as possible from the start.
If j < i, the first element of Si+1 will be greater than the first element of Ti+1, and since the algorithm is greedy, Si+1 will include at least all the elements of Ti+1 not already included by Si.
Now, because of the above, the first element of Si+2 will similarly be greater than the first element of Ti+2, thus Si+2 will include at least all the elements of Ti+2 not already included by previous sets of S. Similarly for the rest of the sets of S and T. Thus there are at least as many sets in T as there are in S.
Thus the set assignment produced by this algorithm can't be any worse than any other assignment. Thus it is optimal.