Geek asks and answers

Find the maximum distance between two points

Yesterday I appeared in an interview. I am stuck in one of the questions and I am asking the same thing here.

There is an array that shows the points on the x axis, there are N points. and M coins.

Remember N >= M

You must maximize the minimum distance between any two points.

Example: Array : 1 3 6 12
         3 coins are given.
         If you put coins on 1, 3, 6 points Then distance between coins are : 2, 3 
         So it gives 2 as answer 
         But we can improve further
         If we put coins at 1, 6, 12 points.
         Then distances are 5, 6
         So correct answer is : 5

Please help me because I am completely stuck on this issue.

+5
source share
3 answers

Here is my approach O (N 2 ) . First create all possible distances;

int dist[1000000][3], ndist = 0;
for(int i = 0; i < n; i ++) {
    for(int j = i + 1; j < n; j ++) {
        dist[ndist][0] = abs(points[i] - points[j]);
        dist[ndist][1] = i; //save the first point
        dist[ndist][2] = j; //save the second point
    }
}

Now sort the distances in descending order:

sort(dist, dist + ndist, cmp);

Where cmp:

bool cmp(int x[], int y[]) {
    return (x[0] > y[0]);
}

Swipe through the array adding dots until you select m:

int chosen = 0;
int ans;
for(int i = 0; i < ndist; i ++) {
    int whatadd = (!visited[dist[i][1]]) + (!visited[dist[i][2]); //how many new points we'll get if we take this one
    if(chosen + whatadd > m) {
        break;
    }
    visited[dist[i][1]] = 1;
    visited[dist[i][2]] = 1;
    chosen += whatadd;
    ans = dist[i][0]; //ans is the last dist[i][0] chosen, since they're sorted in decreasing order
}
if(chosen != m) {
    //you need at most one extra point, choose the optimal available one
    //left as an exercise :)
}

I hope this helps!

+1

gready: ( ). , ( ), . , .

0

You need to use dynamic programming. Because you need an optimal answer. Your problem is similar to the “ Change coin problem” problem . Like the problem, you have no coins, and you want to find the minimum distance (instead of the minimum number of coins).

You can read the following link: Change Coin Problem and Dynamic Programming

-1
source

More articles:


All Articles