Maximize count of persons receiving a chocolate

0 0 6 minutes read

Given two arrays A[], consisting of N integers, and B[], consisting of taste values of M chocolates and an integer X, the task is to find the maximum number of people who can receive a chocolate based on the condition that one person can have only one chocolate and with taste value in the range [A[i] – X, A[i] + X].
Note: Once a chocolate is given to a person, it cannot be given to any other person.

Examples:

Input: A[] = {90, 49, 20, 39, 60}, B[] = {14, 24, 82}, X = 15
Output: 3
Explanation:
1st person can pick the 3rd chocolate as the value of the 3rd chocolate ( = 82 ) lies in the range [75 ( = 90 – 15 ), 105 ( = 90 + 15)].
2nd person can’t pick any chocolate because there is no chocolate with value in the range [34 ( = 49 – 15 ), 64 ( = 49 + 15).
3rd person can pick the 1st chocolate as the value of the 1st chocolate lies in the range [5 ( = 20 – 15), 35 ( = 20 – 15)].
4th person can pick the 2nd chocolate because value of the 2nd chocolate lies in the range [ 24 ( = 39 – 15) and 54 ( = 39 – 15)].
5th person can’t pick any chocolate because there is no chocolate with value in the range [45 ( = 60 – 15), 75 ( = 60 – 15)].
Therefore, the total number of people receiving a chocolate is 3, which is the maximum possible.

Input: A[] = {2, 4, 6, 40, 50}, B[] = {38, 36}, X=13
Output: 2

Approach: This problem can be solved using Greedy Technique/a> and Searching. The key observation here is for any i^th person, assign the chocolate with smallest possible value that lies in the range, if possible. Otherwise, exclude that person from the result. Follow the steps below:

Sort the given arrays A[] and B[] in non-decreasing order.
Initialize a multiset to store the elements of the array B[].
Initialize a variable count = 0, to store the count of persons receiving a chocolate.
Traverse the array A[] and find the smallest possible chocolate value that can be assigned to every i^th person using Binary Search or lower_bound(). Check if that value lies in the range [a_i– X, a_i+ X] or not.
If found to be true, then increment count and remove the value of this chocolate from the multiset.
After completing the above steps, print the value of count as the result.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the maximum number
// of persons receiving a chocolate
int countMaxPersons(int* A, int n, int* B,
                    int m, int x)
{
 
    // Initialize count as 0
    int count = 0;
 
    // Sort the given arrays
    sort(A, A + n);
    sort(B, B + m);
 
    // Initialize a multiset
    multiset<int> s;
 
    // Insert B[] array values into
    // the multiset
    for (int i = 0; i < m; i++)
        s.insert(B[i]);
 
    // Traverse elements in array A[]
    for (int i = 0; i < n; i++) {
        int val = A[i] - x;
 
        // Search for the lowest value in B[]
        auto it = s.lower_bound(val);
 
        // If found, increment count,
        // and delete from set
        if (it != s.end()
            && *it <= A[i] + x) {
            count++;
            s.erase(it);
        }
    }
 
    // Return the number of people
    return count;
}
 
// Driver Code
int main()
{
    int A[] = { 90, 49, 20, 39, 49 };
    int B[] = { 14, 24, 82 };
    int X = 15;
    int N = sizeof(A) / sizeof(A[0]);
    int M = sizeof(B) / sizeof(B[0]);
 
    // Function Call
    cout << countMaxPersons(A, N, B, M, X);
}

Java

import java.util.*;
 
public class Main {
 
    // Function to count the maximum number
    // of persons receiving a chocolate
    public static int countMaxPersons(int[] A, int n, int[] B,
                                      int m, int x) {
 
        // Initialize count as 0
        int count = 0;
 
        // Sort the given arrays
        Arrays.sort(A);
        Arrays.sort(B);
 
        // Initialize a multiset
        TreeSet<Integer> s = new TreeSet<>();
 
        // Insert B[] array values into
        // the multiset
        for (int i = 0; i < m; i++)
            s.add(B[i]);
 
        // Traverse elements in array A[]
        for (int i = 0; i < n; i++) {
            int val = A[i] - x;
 
            // Search for the lowest value in B[]
            Integer it = s.ceiling(val);
 
            // If found, increment count,
            // and delete from set
            if (it != null && it <= A[i] + x) {
                count++;
                s.remove(it);
            }
        }
 
        // Return the number of people
        return count;
    }
 
    public static void main(String[] args) {
        int[] A = {90, 49, 20, 39, 49};
        int[] B = {14, 24, 82};
        int X = 15;
        int N = A.length;
        int M = B.length;
 
        // Function Call
        System.out.println(countMaxPersons(A, N, B, M, X));
    }
}
// This code is provided by mukul ojha

Python3

# Python3 program for the above approach
from bisect import bisect_left
 
# Function to count the maximum number
# of persons receiving a chocolate
def countMaxPersons(A, n, B, m, x):
 
    # Initialize count as 0
    count = 0
 
    # Sort the given arrays
    A = sorted(A)
    B = sorted(B)
 
    # Initialize a multiset
    s = []
 
    # Insert B[] array values into
    # the multiset
    for i in range(m):
        s.append(B[i])
 
    # Traverse elements in array A[]
    for i in range(n):
        val = A[i] - x
 
        # Search for the lowest value in B[]
        it = bisect_left(s,val)
 
        # If found, increment count,
        # and delete from set
        if (it != len(s) and it <= A[i] + x):
            count += 1
            del s[it]
 
    # Return the number of people
    return count
 
# Driver Code
if __name__ == '__main__':
 
    A = [90, 49, 20, 39, 49]
    B = [14, 24, 82]
    X = 15
    N = len(A)
    M = len(B)
 
    # Function Call
    print(countMaxPersons(A, N, B, M, X))
 
    # This code is contributed by mohit kumar 29

C#

// C# program for the above approach
 
using System;
using System.Collections.Generic;
 
public class Program
{
    // Function to count the maximum number
    // of persons receiving a chocolate
    public static int CountMaxPersons(int[] A, int n, int[] B,
                                      int m, int x)
    {
        // Initialize count as 0
        int count = 0;
 
        // Sort the given arrays
        Array.Sort(A);
        Array.Sort(B);
 
        // Initialize a sorted set
        SortedSet<int> s = new SortedSet<int>();
 
        // Insert B[] array values into
        // the sorted set
        for (int i = 0; i < m; i++)
            s.Add(B[i]);
 
        // Traverse elements in array A[]
        for (int i = 0; i < n; i++)
        {
            int val = A[i] - x;
 
            // Search for the lowest value in B[]
            var it = s.GetViewBetween(val, A[i] + x).GetEnumerator();
 
            // If found, increment count,
            // and delete from set
            if (it.MoveNext())
            {
                count++;
                s.Remove(it.Current);
            }
        }
 
        // Return the number of people
        return count;
    }
 
    public static void Main(string[] args)
    {
        int[] A = { 90, 49, 20, 39, 49 };
        int[] B = { 14, 24, 82 };
        int X = 15;
        int N = A.Length;
        int M = B.Length;
 
        // Function Call
        Console.WriteLine(CountMaxPersons(A, N, B, M, X));
    }
}
 
// This code is provided by codebraxnzt

Javascript

// Function to count the maximum number of persons receiving a chocolate
function countMaxPersons(A, n, B, m, x) {
 
  // Initialize count as 0
  let count = 0;
 
  // Sort the given arrays
  A = A.sort((a, b) => a - b);
  B = B.sort((a, b) => a - b);
 
  // Initialize a set
  let s = new Set(B);
 
  // Traverse elements in array A[]
  for (let i = 0; i < n; i++) {
    let val = A[i] - x;
 
    // Search for the lowest value in B[]
    let it = Array.from(s).findIndex(elem => elem >= val);
 
    // If found, increment count,
    // and delete from set
    if (it !== -1 && Array.from(s)[it] <= A[i] + x) {
      count += 1;
      s.delete(Array.from(s)[it]);
    }
  }
 
  // Return the number of people
  return count;
}
 
// Driver Code
let A = [90, 49, 20, 39, 49];
let B = [14, 24, 82];
let X = 15;
let N = A.length;
let M = B.length;
 
// Function Call
console.log(countMaxPersons(A, N, B, M, X));
 
// This code is contributed by Aditya Sharma

Output:

Time Complexity: O(N*log N)
Auxiliary Space: O(M)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!