Example: Candidates - rFronteddu/general_wiki GitHub Wiki

• There are n candidates with the expense to hire them listed in an array. The expense to hire the i'th candidate is cost[i].
• The budget for hiring a pair of new members into our team is between min_cost and max_cost, both inclusive.
• Given the array cost and two integers min_cost and max_cost , find the number of pairs of people whose total expense is between min_cost and max_cost, both inclusive.

import java.util.Arrays;

public class Solution {
    public long getNumTeams(int[] cost, int min_cost, int max_cost) {
        // Sort the cost array
        Arrays.sort(cost);
       
        long count = 0; // To count valid pairs
        int n = cost.length;
       
        // Using two pointers to find pairs
        for (int left = 0; left < n; left++) {
            // For each left candidate, we look for a right candidate
            // such that min_cost <= cost[left] + cost[right] <= max_cost
           
            // Find the first index where cost[left] + cost[right] >= min_cost
            int rightMin = findFirstIndex(cost, left + 1, n - 1, min_cost - cost[left]);
            // Find the first index where cost[left] + cost[right] > max_cost
            int rightMax = findFirstIndex(cost, left + 1, n - 1, max_cost - cost[left]);

            // Count pairs if rightMin is within bounds
            if (rightMin < n && rightMin < rightMax) {
                count += (rightMax - rightMin);
            }
        }
       
        return count;
    }

    // Binary search to find the first index where cost[index] >= target
    private int findFirstIndex(int[] cost, int start, int end, int target) {
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (cost[mid] < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return start; // The first index where cost[index] >= target
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] cost = {1, 2, 3, 4, 5};
        int min_cost = 5;
        int max_cost = 7;

        long result = solution.getNumTeams(cost, min_cost, max_cost);
        System.out.println(result); // Output: 3
    }
}