|
Given two arrays A[] and B[] of size N and M respectively denoting the required elements of each group and the number of elements in a pack respectively. The task is to distribute the maximum number of packs such that the difference in the number of elements received by a group and their requirement is at most K.
Examples:
Input: N = 4, M = 3, K = 5, A[] = [60, 45, 80, 60], B[] = [30, 60, 75]
Output: 2
Explanation: The 2 packs that will be distributed are as follows.
The pack whose size is 60 is distributed among the group with
requirement 60 as 60 – 5 < 60 and 60 + 5 > 60 .
The pack whose size is 75 is distributed among the group with
requirement 80 as 80 – 5 = 75 and 80 + 5 > 75.
Input: N = 4, M = 3, K = 10, A[] = [60, 40, 80, 60], B[] = [30, 60, 75]
Output: 3
Explanation: All the packs will be distributed in this situation .
The pack whose size is 30 is distributed among the group with
requirement 40 as 40 – 10 = 30 and 40 + 10 > 30.
The pack whose size is 60 is distributed among the group with
requirement 60 as 60 – 10 < 60 and 60 + 10 > 60.
The pack whose size is 75 is distributed among the group with
requirement 80 as 80 – 10 < 75 and 80 + 10 > 75.
Approach: The problem can be solved using sorting based on the following idea:
Sort both arrays. Now greedily find out the first group with a requirement that is fulfilled and among all the possible packs, allot the pack with minimum number of elements so that options are available for groups with higher requirements.
Follow the steps mentioned below to implement the idea:
- Sort array A[] and B[].
- After sorting both arrays use two pointers i and j to iterate A and B respectively.
- Initialize a variable (say cnt = 0) to store the answer.
- Now start iterating through the arrays:
- If the pack size is desired for the group then increment cnt, i and j.
- If the requirement of the group after subtracting the maximum difference K is greater than pack size then this pack is not useful for any group. Hence increment j.
- If the pack size is greater than the requirement of the group after adding K, then there is no pack for that group. Hence increment i.
- Return the cnt variable as the required answer.
Below is the implementation of the above approach.
C++
<?php
function desired_size($N, $M, $K, $A, $B)
{
sort($A);
sort($B);
$i = 0;
$j = 0;
$cnt = 0;
while ($i < $N && $j < $M) {
if ($A[$i] - $K <= $B[$j] && $A[$i] + $K >= $B[$j]) {
$cnt++;
$i++;
$j++;
}
else if ($A[$i] - $K > $B[$j]) {
$j++;
}
else if ($A[$i] + $K < $B[$j]) {
$i++;
}
}
return $cnt;
}
$N = 4;
$M = 3;
$K = 5;
$A = array( 60, 45, 80, 60 );
$B = array( 30, 60, 75 );
echo desired_size($N, $M, $K, $A, $B);
?>
|
Time Complexity: O(D * logD) where D is the maximum between N and M
Auxiliary Space: O(1)
|
