The algorithm for finding the narrowest intervals, m of which will cover a set of numbers

Question

Say you have a list of numbers n . You are allowed to choose m integers (allows you to call the integer a ). For each integer a, delete all numbers within the included range [ a - x, a + x ], where x is the number. What is the minimum value of x that the list can clear?

For example, if your list of numbers was

1 3 8 10 18 20 25

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

You can select two integers 5 and 20. This will clear the list as it removes each number between [5-5, 5 + 5] and [20-5, 20 + 5].

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

The code will be really useful, preferably in Java or C ++ or C.

Answer 1

Recursive solution:

-, , m , (x) ~ ( - )/2 * m. (x) . , x, (x) ! , . , : , ​​ , . , , .

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:

: . "" . , "m" .

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<long[]> 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 2

,

1 3 8 10 18 20 25

, , x 2.

, 1 + x (1 - ). 1 + x + x = 5. , .

, 8, 8 + x = 10 10 + x = 12 .

, [18,24], [25,29].

x 4 . , x .

x, m .

Answer 3

( ) →

• . mp.

• "last_element - first_element + 1" , , "ans".

• 'x' 'ans/2'.

, , .

Answer 4

, . , k-mean: m- x , .

Answer 5

1) BEST CASE, AVERAGE CASE WORST CASE TIME SPACE.

2) , . ( )

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 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