Legendary Magician

4.5

2 votes
Algorithms, Greedy Algorithms, Basics of Greedy Algorithms, Greedy algorithm
Problem

Legendary magician, Dynamo has a special magic trick that he wants to show to every student in College. But as this is placement time, every student is busy with preparation, so everyone can't be present at the magic show at the same time. There are N students in college, and the ith student reaches the magic show at a time Ai and leaves at time Bi . As special trick is so special, he doesn't want to play it frequently. So, Dynamo wants to know the minimum number of times he would have to show his special trick so that every student in college can watch this.

Note: To play the magic trick, he takes 0 seconds.

 

Input Format

The first line of the input contains an integer T, denoting the number of test cases.

The first line of test case contains a single integer N - denoting the length of array A and B.

The second line of test case contains N space separated integers, A1,A2,A3,....,AN

The third line of test case contains N space separated integers, B1,B2,B3,....,BN

 

Output Format

Return an integer denoting the minimum number of times Dynamo would have to play his special trick .

 

Constraints

1T1001N1051A[i]<B[i]109

Both A[i] and B[i] are inclusive.

The sum of N over all test cases does not exceed 105

Time Limit: 3
Memory Limit: 256
Source Limit:
Explanation

Tese case 1 :If Dynamo shows his magic trick at time 7 and 8, all the student will be able to see it. At time 7 student 2 and 3 willl be there to see and at time 8 student 1 will come to see.

Tese case 2 : If Dynamo shows his magic trick at time 5, 8 and 10 all the student will be able to see it.At time 5 student 2 and 3 will be there to see, and at time 8 student 1 will come to see and at time 10 student 4 will come to see.

Editor Image

?