Prisoner and jailer | Binary Search Problem

In a prison, there are N cells. The positions of the cells are given in an array. The Jailer has to place all the prisoners in the cells in an ordered manner such that minimum distance between any two prisoners is as large as possible. You have to find that distance.

Note: The cells are in a straight line. So the positions of cells can be considered as the points on x-axis.

Constraints:

2 <= N <= 100000 (N is the number of cells in a prison)
0 <= pi <= 1000000000 (pi is the position of a cell)
2 <= P <= N (P is the number of prisoners)

Examples:

Input : N = 5, P = 3
Cells position: 1, 2, 8, 4, 9
 
Output: 3
Here, the first prisoner can be kept in a cell at position 1.
Second prisoner can be kept in a cell at position 4.
Third prisoner can be kept in a cell at position 8.

This way we can place all the prisoners and the largest minimum separation between any two prisoners is 3, between prisoner 1 and 2, as we placed first at position 1, and second at position 4. So the separation between them is 3 whereas the distance between other prisoners is 4 and 7, but the largest minimum separation between any two prisoners is 3.

Approach:
We are going to use Binary Search Algorithm to solve this problem. As we have to find the largest minimum distance between two cells in which prisoners will be kept, our search space will be of distance, starting from 0(if two prisoners are kept in the same cell, then distance between them is 0) and end will be cells[n-1]-cells[0] (if one prisoner is kept in the first cell, and the other one is kept in the last cell).

We are going to check whether the prisoner can be kept at a cell or not till start <= end.
First we find the middle element, and check if it possible to place all the prisoners taking middle element of search space as the minimum separation.
If we cannot place all the prisoners, at that separation we reduce our search space by making end = mid-1, because if it is not possible to place the prisoners at separation = mid, then it is impossible to keep the prisoners at separation > mid.
If all the prisoners are placed at separation = mid, we make start = mid+1, so that we can look for even better answers i.e greater separation.

The problem is easy to understand, follow the comments and dry run the code once.

// C++ program of Prisoners and Jailer problem (Binary search)

#include <bits/stdc++.h>
using namespace std;

bool canPlace(int a[], int n, int p, int sep) {
    // Considering the first prisoner is placed at the 1st cell
    int prisoners_placed = 1;

    // First prisoner is placed at cell[0]
    int last_prisoner_placed = a[0];  

    for (int i = 1; i < n; i++) {
        int current_cell = a[i];

        // Checking if the prisoner can be placed at the ith cell or not
        if (current_cell - last_prisoner_placed >= sep) {
            prisoners_placed++;
            last_prisoner_placed = current_cell;

            // If all prisoners are placed, return true
            if (prisoners_placed == p) {
                return true;
            }
        }
    }
    return false;
}

int main() {
    int n = 5; // Number of cells
    int p = 3; // Number of prisoners
    int cells[5] = {1, 2, 8, 4, 9};

    // Sort the array to enable binary search
    sort(cells, cells + n);

    int start = 0;

    // Search space for the minimum distance
    int end = cells[n - 1] - cells[0];

    int ans = 0;
    while (start <= end) {
        int mid = (start + end) / 2;

        // Check if prisoners can be placed with 'mid' as the minimum separation
        if (canPlace(cells, n, p, mid)) {
            ans = mid; // Update the answer
            start = mid + 1; // Try for a larger minimum separation
        } else {
            end = mid - 1; // Try for a smaller separation
        }
    }

    cout << "Largest minimum separation can be " << ans << endl;
    return 0;
}

Output:

Largest minimum separation can be 3