The scholars party
All submissions for this problem are available.
In the field of algorithmic research, a researcher is recognized by the number of years(Y) he/she has been working as a professor in an educational institution of national importance, and the number of research papers(P) he/she has published in international journals. Any two researchers i and j hate each other if one of the following conditions, holds
- Yi >= Yj and Pj >= Pi
- Yj >= Yi and Pi >= Pj
If both the attributes of a researcher i, are strictly greater than those of researcher j, then i is so eminent for j that i will ignore j and j will respect i.
The president of ACM, Mr. X is throwing a party on the occasion of his son graduating as a Ph.D in Computer Science. He has a list of researchers he wants to invite but he doesn't want to invite them all because after a couple of drinks the haters may start heated discussions and hence will spoil the party. So he wants to choose a subset of the researchers such that no two of them hate each other. As his student, help him find how many people he can invite at max.
First line of input is the number of researchers n that he knows, after which n lines follow each representing the attributes of a researchers separated by a space i.e. Y P.
Single integer i.e. the maximum number of people that can be invited in the party.
- 1 <= n <= 10000
Input: 4 1 4 2 3 5 2 4 3 Output: 1
Input: 6 2 3 3 5 3 7 4 6 4 8 5 7 Output: 4
|Time Limit:||0.217617 - 0.65285 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, PERL, ASM, CLPS, PRLG, SCM qobi, LUA, BASH, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, PYP3, CLOJ|
Fetching successful submissions
If you are still having problems, see a sample solution here.