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

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

Let's say you have a list of n numbers. You are allowed to choose m integers (lets call the integer a). For each integer a, delete every number that is within the inclusive range [a - x, a + x], where x is a number. What is the minimum value of x that can get the list cleared?

For example, if your list of numbers was

1 3 8 10 18 20 25

and m = 2, the answer would be x = 5.

You could pick the two integers 5 and 20. This would clear the list because it deletes every number in between [5-5, 5+5] and [20-5, 20+5].

How would I solve this? I think the solution may be related to dynamic programming. I do not want a brute force method solution.

Code would be really helpful, preferably in Java or C++ or C.

Answer by Vimal for Algorithm to find the narrowest intervals, m of which will cover a set of numbers

An effective algorithm can be(assuming list is sorted) ->

1. We can think of list as groups of 'm' integers.

2. Now for each group calculate 'last_element - first_element+1', and store maximum of this value in a variable say, 'ans'.

3. Now the value of 'x' is 'ans/2'.

I hope its pretty clear how this algorithm works.

Answer by Dweller for Algorithm to find the narrowest intervals, m of which will cover a set of numbers

I think it's similarly problem of clusterization. For example You may use k-means clustering algorithm: do partitions of initial list on m classes and for x get maximum size divided by two of obtained classes.

Answer by Peter de Rivaz for Algorithm to find the narrowest intervals, m of which will cover a set of numbers

Hints

Suppose you had the list

1 3 8 10 18 20 25  

and wanted to find how many groups would be needed to cover the set if x was equal to 2.

You could solve this in a greedy way by choosing the first integer to be 1+x (1 is the smallest number in the list). This would cover all elements up to 1+x+x=5. Then simply repeat this process until all numbers are covered.

So in this case, the next uncovered number is 8, so we would choose 8+x=10 and cover all numbers up to 10+x=12 in the second group.

Similarly, the third group would cover [18,24] and the fourth group would cover [25,29].

This value of x needed 4 groups. This is too many, so we need to increase x and try again.

You can use bisection to identify the smallest value of x that does cover all the numbers in m groups.

Answer by David Prez Cabrera for Algorithm to find the narrowest intervals, m of which will cover a set of numbers

A recursive solution:

First, you need an estimation, you can split in m groups, then estimated(x) must be ~ (greather - lower element) / 2*m. the estimated(x) could be a solution. If there is a better solution, It has lower x than extimated(x) in all groups! and You can check it with the first group and then repeat recursively. The problem is decreasing until you have only a group: the last one, You know if your new solution is better or not, If there'is better, you can use it to discard another 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;          for (int i = begin + 1; i <= end + 1 - m; i++) {              // It split the 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 {                  i = 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, It search for "islands" of distances and split the problem into different islands. like divide and conquer, It distribute 'm' into 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;          for (int i = begin + 1; i <= 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 {                  i = end;              }          }          return bestX;      }  }    private static long solver(long[] n, long m,  int begin, int end) {      long estimate = estimate(n, m, begin, end);      PriorityQueue islands = new PriorityQueue<>((p0, p1) -> Long.compare(p1[0], p0[0]));      int islandBegin = begin;      for (int i = islandBegin; i < 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];      for (int i = 1; i < 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));  }  

Answer by plainOldNerd for Algorithm to find the narrowest intervals, m of which will cover a set of numbers

1) You should look into BEST CASE, AVERAGE CASE and WORST CASE complexities with regards to TIME and SPACE complexities of algorithms.

2) I think David Prez Cabrera has the right idea. Let's assume average case (as in the following pseudo code)

3) Let the list of integers be denoted by l

    keepGoing = true      min_x = ceiling(l[size-1]-l[0])/(2m)        while(keepGoing)      {          l2 = l.copy          min_x = min_x-1          mcounter = 1            while(mcounter <= m)          {              firstElement = l2[0]  //  This while condition will likely result in an ArrayOutOfBoundsException  //  It's easy to fix this.                while(l2[0] <= firstElement+2*min_x)              {   remove(l2[0])   }              mcounter = mcounter+1          }          if(l2.size>0)              keepGoing = false      }      return min_x+1  

4) Consider

l = {1, 2, 3, 4, 5, 6, 7}, m=2 (gives x=2)  l = {1, 10, 100, 1000, 10000, 100000, 1000000}, m=2  l = {1, 10, 100, 1000, 10000, 100000, 1000000}, m=3  

Fatal error: Call to a member function getElementsByTagName() on a non-object in D:\XAMPP INSTALLASTION\xampp\htdocs\endunpratama9i\www-stackoverflow-info-proses.php on line 72