New Employees
InterviewTime limit2sMemory limit256 MB
Given N applicants ranked by two criteria, count applicants not dominated in both ranks by any other applicant (classic sort plus max-suffix pattern).
Problem
A company is hiring new employees. Each applicant has two ranks: a document-screening rank and an interview rank.
The company does not hire an applicant if another applicant is better in both ranks. In other words, if there exists an applicant B whose document-screening rank and interview rank are both better than applicant A's, then A cannot be hired.
Find the maximum number of new employees the company can hire while following this rule.
Input
The first line contains the number of test cases T (1 <= T <= 20).
For each test case, the first line contains the number of applicants N (1 <= N <= 100,000). Each of the next N lines contains two integers: an applicant's document-screening rank and interview rank.
Each rank is a permutation of the integers from 1 through N with no ties. A smaller rank is better.
Output
For each test case, print the maximum number of new employees that can be hired on its own line.