Good thoughtful question on Binary search on answers

Problem link: https://leetcode.com/problems/maximize-score-of-numbers-in-ranges/description/

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

    }

}