PROBLEM LINK:Author: Subham Das DIFFICULTY:EASY PREREQUISITES:Array, Sorting PROBLEM:Given two integer arrays C and D both of length N, establish a onetoone correspondence between the elements of C and D so as to maximize the number of pairings where the element of C is greater than the element from D in a pair. EXPLANATIONThe value of n and the array C, D which contains the power of Chef's cards and Devu's cards respectively are given within every test case. The first step would be to sort the array C and D in increasing order. Then number of times Chef's cards have more value than Devu's cards can be found out with the help of the following greedy algorithm: j = 0; for i 0 to n1 if(C[i] > D[j]) j = j+1; After this printing the value of j would yield the answer as (j1) is the maximum value upto which all values of array D are lesser than some corresponding value in array C. Complexity: $\mathcal{O}(N\, log\, N)$ AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here.
This question is marked "community wiki".
asked 14 Oct '16, 23:11
