A coach of a school chess club wants to start a mentoring program for newer players. Each player has an integer rating representing skill level. The coach would like to pair up students whose ratings differ by no less than a given minimum. What is the maximum number of pairs that can be formed?
for ex: n=6; rating=[1,2,3,4,5,6]; minDiff=4; ans: 2; explaination: There are Two pairs of players have a difference of 4 or more; those ratinggs are (1,5) and (2,6)
Constraints: 1<=n<=2*10^5 0<=rating[i]<=10^9 0<=minDiff<=10^9
This was asked in Hackerank intermediate certification Test.I failed to come up with a solution better than quadratic.
Please specify reason before downvoting the post? whether information is missing or i asked the wrong way? This will myself to ask in better manner in future posts.
Maybe it's because you pasted the question into a coding block... Use plain text format for question.
The solution would be to sort the array in ascending order and then for each player find the next player with the least skill that satisfies the minimum criteria. Use binary search to find the next optimal player.
Sort the array in ascending order.
for ex: n=8; rating=[14,18,30,45,43,2,8,3]; minDiff=4;
After sorting [2,3,8,14,18,30,43,45]
Answer is in bold: [2,3,8,14,18,30,43,45]
It can be solved with greedy approach
Pseudo Code:
Array is sorted in ascending order.
int i=0; int Pairs=0;
while(i+1 < n)
{
if(abs(A[i]-A[i+1]) <= minDiff)
Pairs++; i+=2;
else
i++;
} PS: Sorry I understood question in wrong way.
It is a minDiff, not a maxDiff. You need a second pointer and solve it with 2 pointers after sorting the array.
Codeforces also got almost same question. It can be solved by using binary search. Here is the link of question
https://codeforces.me/contest/1156/problem/C
And editorial link:
https://codeforces.me/blog/entry/66827