Solution:
//import java.util.Arrays;
class Solution {
public int maxPossibleScore(int[] start, int d) {
Arrays.sort(start); // Ensure the start array is sorted
long head = 0, tail = (long) 2e9;
while (head < tail) {
long mid = (head + tail + 1) / 2; // Try the middle gap value
if (check(mid, start, d)) {
head = mid; // Gap is valid, try for a larger gap
} else {
tail = mid - 1; // Gap is not valid, reduce the gap
}
}
return (int) head; // Maximum minimum gap found
}
// Function to check if a given gap 'lim' is valid
public static boolean check(long lim, int[] start, int d) {
long now = start[0]; // Start with the first number
// for each mid you are checking whether it is within the range of each
// interval and if it is then you are checking with greater gap that is
// mid value otherwise if not then you are reducing by mid-1
for (int i = 1; i < start.length; i++) {
now = Math.max(now + lim, start[i]); // Pick the maximum valid number
if (now > start[i] + d) return false; // If exceeds the range, return false
}
return true; // Gap is valid for all picks
}
}
