There are N tutors who have been assigned to teach N students in a mathematics class. Every tutor's and student's knowledge about mathematics can be defined by a pair of values: A (Algebra) and G (Geometry)All the A values are pairwise distinct, and similarly, all the G values are pairwise distinct.
A tutor t can teach a student s if and only if G_{t} > G_{s} and A_{t} > A_{s}. Find the maximum number of tutor-student pairings which follow the above condition.
Input Format
The first line contains a single integer N (1 <= N <= 2 * 10 ^ 5) denoting the number of students and the number of tutors both.
The next N lines describe the students and contain two integers A (1 <= A <= 10 ^ 9) and G(1 <= G <= 10 ^ 9) per line denoting the algebra and the geometry skill values for each student.
The next N lines describe the tutors and contain two integers A (1 <= A <= 10 ^ 9) and G(1 <= G <= 10 ^ 9) per line, denoting the algebra and the geometry skill values for each tutor
Output Format
Output maximum number of tutor-student pairings satisfying the condition
Auto comment: topic has been updated by Dinocoder (previous revision, new revision, compare).
I will talk about the concept of the solution, not about its implementation, it is possible to implement this algorithm more conveniently.
1) Let's throw pairs of characteristics {A, G} of all 2N people into one array V with notes to whom the characteristic (t or s) belongs, and sort by the first element (A). Imagine V as a tower in which pairs go from bottom to top in ascending order A. We can throw out all the top students, because any teacher has less knowledge in algebra than any of them (it follows from the sorting of the array V).
2) Now there is a block of teachers at the top of the array. Let's go down the nim (before we reach the student) and add their "G_{ti}" to the set.
3) Now the block of students. We know that any of them can be given as a mentor in algebra by any of the teachers from our set (it follows from the sorting of the array V). Now it remains to fulfill the condition G_{t} > G_{s}, for this we will sort this block of students by the second element of the pair (G), and we will go from the bottom, pairing the current student with the teacher with the smallest G_{t} exceeding G_{s} from our set. We remove this teacher from the set.
4) Again a block of teachers. Just add to the existing set G every teacher we meet until we get down to the student.
5) Then we do 3), 4) until we reach the bottom of V.
Сomplexity O(n*log(n))
We always pair the teacher with the student in the best way (the minimum difference in knowledge of geometry, moreover, the teacher knows more about algebra. And other teachers have either been used before, or they know less than a student in algebra, or they have a difference in knowledge of geometry is not minimal), which means the algorithm will find the best solution.