All submissions for this problem are available.
Aman a 2nd year student has to set-up a stall at Technofest '15.
The stall is set for N days and only one person can work at the stall at a time.
There are M first year students who are willing to work at the stall.
Each of them is available for a different duration of time, from some day a to day b.
If assigned work he/she arrives at the stall on day a and waits for the stall to be vacated(if occupied).
If the stall is vacated he works till day b. If not, he returns home on day b and is disappointed.
How many first year students can be assigned work such that no student is disappointed.
NOTE: Student who arrives first at the stall gets to work first.
If two students arrive on the same day one with shorter availability works first.( so that they both get to work at the stall)
Example : say the stall is up for 7 days and there are 4 students who are available as follows
Student 1 : Day 2 to Day 5
Student 2 : Day 1 to Day 6
Student 3 : Day 3 to Day 4
Student 4 : Day 3 to Day 7
At most 2 students can be assigned work, 1 and 4 OR 2 and 4.
If 1 and 2 are assigned work, student 2 will arrive on day 1 and work till day 6.
Student 1 will arrive on day 2 and return on day 5 disappointed.
First line contains no. of test cases.
Second line contains two space separated integers denoting N( no of days the stall is up) and M(no. of willing 1st year students).
Next M lines contains 2 space separated integers a and b, denoting the period during which they are available, i.e., from day a to day b.
Output the the result of each testcase, one in each line.
1<= T <= 10
1<= N <= 10000
1<= M <= 10000
1<= a,b <= M
Input: 1 7 4 2 5 1 6 3 4 3 7 Output: 2
Same as explained above.
|Time Limit:||10 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.