BerSU Ball

Statement : Ball

Editorial :

Let’s quickly analyze the problem statement ….
we have n boy and m girl and we need to match them following a certain constraint :
. For each boy, we know his dancing skills. Similarly, for each girl we know her dancing skills and we need to find the number of pairs such that each pair must differ by at most one.
there is about 1001 way to solve the problem following several approaches for example :
. Maximum bipartie matching
. Dynamic Programming
. Greedy algorithm

I’ll be covering a greedy approach in this editorial hopefully i’ll get some comments to discuss another solution.
We can assume that the maximal number of pairs is equal to min(n,m) …
First let’s sort the arrays of skills and then we can search for pairs such that the absolute difference between a boy’s skill and a girl’s <=1, to do that we need two for loops and for each skill in the first array we take the minimum possible skill in the second array and then we mark the index of the second array as used and break the loop we repeat this min(n,m) time.
In Brief the time complexity of my solution is O(n*m) per test case .
Problem’s link: Ball
Code : Solution
Comments and feedback are welcome

Thank you ;