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++ Implementation:
// 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 1st cell
int prisoners_placed = 1;
// if the first prisoner is placed at the first cell,
// then last_prisoner_placed will be the first prisoner placed
// and that will be in 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 the prisoners are placed, we return true
if (prisoners_placed == p)
{
return true;
}
}
}
return false;
}
int main()
{
int n = 5;
int p = 3;
int cells[5] = {1, 2, 8, 4, 9};
// We apply Binary Search on Sorted Arrays
// so the array becomes 1, 2, 4, 8, 9
sort(cells, cells + n);
int start = 0;
// Search Space of distance.
// Starting distance = 0,
// when two prisoners placed in the same cell.
// Max distance is when the 1st prisoner is placed
// on the 1st cell and the other one is placed on the last cell
int end = cells[n - 1] - cells[0];
int ans = 0;
while (start <= end)
{
int mid = (start + end) / 2;
// Checking if the prisoner can be placed or not
// So that the ans can be updated
// if some other distance greater than ans
// is found during the next search
if (canplace(cells, n, p, mid))
{
ans = mid;
start = mid + 1;
}
else
{
end = mid - 1; // if the prisoner can't be placed
// we reduce the separation by
// making end as mid-1.
}
}
cout << "Largest minimum separation can be " << ans << endl;
return 0;
}
Output:
Largest minimum separation can be 3