Freshers Task

All submissions for this problem are available.
Aman a 2nd year student has to setup 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.
Input
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
Output the the result of each testcase, one in each line.
Constraints
1<= T <= 10
1<= N <= 10000
1<= M <= 10000
1<= a,b <= M
Example
Input: 1 7 4 2 5 1 6 3 4 3 7 Output: 2
Explanation
Same as explained above.
Author:  vedantbajaj96 
Tags  vedantbajaj96 
Date Added:  12122015 
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 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 