java - Algorithm to find the narrowest intervals, m of which will cover a set of numbers -

let's have list of n numbers. allowed choose m integers (lets call integer a). each integer a, delete every number within inclusive range [a - x, + x], x number. minimum value of x can list cleared?

for example, if list of numbers

1 3 8 10 18 20 25

and m = 2, answer x = 5.

you pick 2 integers 5 , 20. clear list because deletes every number in between [5-5, 5+5] , [20-5, 20+5].

how solve this? think solution may related dynamic programming. not want brute force method solution.

code helpful, preferably in java or c++ or c.

a recursive solution:

first, need estimation, can split in m groups, estimated(x) must ~ (greather - lower element) / 2*m. estimated(x) solution. if there better solution, has lower x extimated(x) in groups! , can check first group , repeat recursively. problem decreasing until have group: last one, know if new solution better or not, if there'is better, can use discard worse solution.

private static int estimate(int[] n, int m, int begin, int end) {     return (((n[end - 1] - n[begin]) / m) + 1 )/2; }  private static int calculate(int[] n, int m, int begin, int end, int estimatedx){     if (m == 1){         return estimate(n, 1, begin, end);     } else {         int bestx = estimatedx;         (int = begin + 1; <= end + 1 - m; i++) {             // split problem:             int firstgroupx = estimate(n, 1, begin, i);             if (firstgroupx < bestx){                 bestx = math.min(bestx, math.max(firstgroupx, calculate(n, m-1, i, end, bestx)));             } else {                 = end;             }         }         return bestx;     } }  public static void main(string[] args) {     int[] n = {1, 3, 8, 10, 18, 20, 25};     int m = 2;     arrays.sort(n);     system.out.println(calculate(n, m, 0, n.length, estimate(n, m, 0, n.length))); } 

edit:

long numbers version: main idea, search "islands" of distances , split problem different islands. divide , conquer, distribute 'm' islands.

private static long estimate(long[] n, long m, int begin, int end) {     return (((n[end - 1] - n[begin]) / m) + 1) / 2; }  private static long calculate(long[] n, long m, int begin, int end, long estimatedx) {     if (m == 1) {         return estimate(n, 1, begin, end);     } else {         long bestx = estimatedx;         (int = begin + 1; <= end + 1 - m; i++) {             long firstgroupx = estimate(n, 1, begin, i);             if (firstgroupx < bestx) {                 bestx = math.min(bestx, math.max(firstgroupx, calculate(n, m - 1, i, end, bestx)));             } else {                 = end;             }         }         return bestx;     } }  private static long solver(long[] n, long m,  int begin, int end) {     long estimate = estimate(n, m, begin, end);     priorityqueue<long[]> islands = new priorityqueue<>((p0, p1) -> long.compare(p1[0], p0[0]));     int islandbegin = begin;     (int = islandbegin; < end -1; i++) {         if (n[i + 1] - n[i] > estimate) {             long estimatedisland = estimate(n, 1, islandbegin, i+1);             islands.add(new long[]{estimatedisland, islandbegin, i, 1});             islandbegin = i+1;         }     }     long estimatedisland = estimate(n, 1, islandbegin, end);     islands.add(new long[]{estimatedisland, islandbegin, end, 1});     long result;     if (islands.isempty() || m < islands.size()) {         result = calculate(n, m, begin, end, estimate);     } else {             long mfree = m - islands.size();         while (mfree > 0) {             long[] island = islands.poll();             island[3]++;             island[0] = solver(n, island[3], (int) island[1], (int) island[2]);             islands.add(island);             mfree--;         }         result = islands.poll()[0];     }     return result; }  public static void main(string[] args) {     long[] n = new long[63];     (int = 1; < n.length; i++) {         n[i] = 2*n[i-1]+1;     }     long m = 32;     arrays.sort(n);     system.out.println(solver(n, m, 0, n.length)); }