N one dimensional kingdoms are represented as intervals of the form [ai , bi] on the real line.
A kingdom of the form [L, R] can be destroyed completely by placing a bomb at a point x on the real line if L ≤ x ≤ R.
Your task is to determine minimum number of bombs required to destroy all the one dimensional kingdoms.
Input
First line of the input contains T denoting number of test cases.
For each test case, first line contains N denoting the number of one dimensional kingdoms.
For each next N lines, each line contains two space separated integers ai and bi.
Output
For each test case , output an integer denoting the minimum number of bombs required.
Constraints
Subtask 1 (20 points) : 1 ≤ T ≤ 100 , 1 ≤ N ≤ 100 , 0 ≤ ai ≤ bi ≤500
Subtask 2 (30 points) : 1 ≤ T ≤ 100 , 1 ≤ N ≤ 1000 , 0 ≤ ai ≤ bi ≤ 1000
Subtask 3 (50 points) : 1 ≤ T ≤ 20 , 1 ≤ N ≤ 105, 0 ≤ ai ≤ bi ≤ 2000
Example
Input:
1
3
1 3
2 5
6 9
Output:
2
Explanation
There are three kingdoms [1,3] ,[2,5] and [6,9]. You will need at least 2 bombs
to destroy the kingdoms. In one of the possible solutions, you can place two bombs at x = 2 and x = 6 .
#include
inline long get_input()
{
long num=0,sign=1;
char d = getchar_unlocked();
if(d == ‘-‘)
sign = -1;
while((d’9′) && d!=EOF && d!=’-‘)
d = getchar_unlocked();
if(d == ‘-‘)
sign = -1, d=getchar_unlocked();
while(d>=’0′ && d<=’9’)
{
num = (num<<3)+(num<<1)+(d-‘0’);
d = getchar_unlocked();
}
return sign*num;
}
int main(void) {
int a[2][100000],x1,x2,L,R;
long N,t,bmb,T,count;
T = get_input();
while(T–)
{
N = get_input();
t = 1;
L = get_input();
R = get_input();
count = 0;
bmb = 1;
while(t<N)
{
x1 = get_input();
x2 = get_input();
if(x1=R)
{
L = L;
R = R;
}
else if(x1>=L&&x1=R)
{
L = x1;
}
else if(x1>=L&&x2<=R)
{
L = x1;
R = x2;
}
else if(x1<=L&&x2=L)
{
R = x2;
}
else
{
a[0][count] = x1;
a[1][count] = x2;
count++;
}
t++;
}
N = count;
while(N>0)
{
t = 1;
count = 0;
L = a[0][0];
R = a[1][0];
while(t<N)
{
x1 = a[0][t];
x2 = a[1][t];
if(x1=R)
{
L = L;
R = R;
}
else if(x1>=L&&x1=R)
{
L = x1;
}
else if(x1>=L&&x2<=R)
{
L = x1;
R = x2;
}
else if(x1<=L&&x2=L)
{
R = x2;
}
else
{
a[0][count] = x1;
a[1][count] = x2;
count++;
}
t++;
}
bmb++;
N = count;
}
printf(“%ld\n”,bmb);
}
return 0;
}
Code N Solve 