Given two arrays A[] and B[] of dimension N and M respectively denoting the required parts of every group and the variety of parts in a pack respectively. The duty is to distribute the utmost variety of packs such that the distinction within the variety of parts acquired by a gaggle and their requirement is at most Ok.
Examples:
Enter: N = 4, M = 3, Ok = 5, A[] = [60, 45, 80, 60], B[] = [30, 60, 75]
Output: 2
Rationalization: The two packs that shall be distributed are as follows.
The pack whose dimension is 60 is distributed among the many group with
requirement 60 as 60 – 5 < 60 and 60 + 5 > 60 .
The pack whose dimension is 75 is distributed among the many group with
requirement 80 as 80 – 5 = 75 and 80 + 5 > 75.Enter: N = 4, M = 3, Ok = 10, A[] = [60, 40, 80, 60], B[] = [30, 60, 75]
Output: 3
Rationalization: All of the packs shall be distributed on this situtation .
The pack whose dimension is 30 is distributed among the many group with
requirement 40 as 40 – 10 = 30 and 40 + 10 > 30.
The pack whose dimension is 60 is distributed among the many group with
requirement 60 as 60 – 10 < 60 and 60 + 10 > 60.
The pack whose dimension is 75 is distributed among the many group with
requirement 80 as 80 – 10 < 75 and 80 + 10 > 75.
Method: The issue might be solved utilizing sorting based mostly on the next concept:
Type each arrays. Now greedily discover out the primary group with a requirement that’s fulfilled and amongst all of the attainable packs, allot the pack with minimal variety of parts in order that choices can be found for teams with greater necessities.
Observe the steps talked about under to implement the concept:
- Type array A[] and B[].
- After sorting each arrays use two pointers i and j to iterate A and B respectively.
- Initialize a variable (say cnt = 0) to retailer the reply.
- Now begin iterating by the arrays:
- If the pack dimension is desired for the group then increment cnt, i and j.
- If the requirement of the group after subtracting the utmost distinction Ok is larger than pack dimension then this pack just isn’t helpful for any group. Therefore increment j.
- If the pack dimension is larger than the requirement of the group after including Ok, then there isn’t any pack for that group. Therefore increment i.
- Return the cnt variable because the required reply.
Under is the implementation of the above strategy.
C++
|
|
Time Complexity: O(D * logD) the place D is the utmost between N and M
Auxiliary House: O(1)
