To get to the treasure, Jones must complete one more task. He comes across a table, where there are a number of wooden planks lying along the length of the table. He notices that the width of the table is exactly equal to the width of every plank on it. The planks are so heavy that they cannot be manually moved in any way. Some of these wooden planks are overlapping. Jones has a hammer and the Gods grant him infinite nails. The planks have to be joined to the table with nails such that every plank is connected to the table through at least one nail. The nails are of sufficient length, and have to be hammered vertically into the table. One or more planks can be joined to the table through a single nail provided they have a common overlap. Find out the minimum number of nails he needs to nail all planks to the table.

• The first line of the input is a positive integer t <= 20, denoting the number of tables.
• The descriptions of the table follow one after the other.
• Table description:
  • The first line of the description of the k^th table contains a positive integer n (n <= 10010), the number of planks on it.
  • This is followed by n lines containing the description of the planks.
  • The description of each plank is a pair of integers a and b (0 <= a <= b <= 10000010), denoting the distance of the left end and right end of the plank from the left end of the table.

The output must contain t lines , the k^th line corresponding to the k^th table. The output on the k^th line must be an integer i_k, the minimum number of nails required.

Input: 
2 
3 
1 5 
3 5 
2 4 
2 
1 4 
4 5

Output: 
1 
1

#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>using namespace std;#define INF  0x3f3f3f#define size 100020 struct node{    int a,b;}t[size];int cmp(const node i,const node j){    return i.a<j.a;}int main(){    int n,m;    cin>>n;    while(n--)    {        cin >> m;        for(int i =0;i < m;i++)        {            cin>> t[i].a>>t[i].b;        }        sort(t,t+m,cmp);        //cout<< t[0].a<< t[1].a<< t[2].a;        int x=INF,y=INF,k=1;        for(int i =0;i<m;i++)        {            if(y<t[i].a){                k++;                y = t[i].b;            }            x= t[i].a;            if(y>t[i].b)y = t[i].b;        }        cout<< k<< endl;    }    return 0;}

#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int maxn = 10100;struct Table{    int l,r;    bool operator < (const Table &rhs) const{        return r < rhs.r;    }}table[maxn];int main(){    int kase,n;    scanf("%d",&kase);    while(kase--){        scanf("%d",&n);        for(int i = 0;i < n;i++){            scanf("%d%d",&table[i].l,&table[i].r);        }        sort(table,table+n);        int ans = 0,r = -1;        for(int i = 0;i < n;i++){            if(r < table[i].l){                ans++;                r = table[i].r;            }        }        printf("%d\n",ans);    }    return 0;}

#include <iostream>#include<cstdio>#include<algorithm>using namespace std;struct plank{    int a,b;} p[10015];bool cmp(struct plank p1,struct plank p2){    if(p1.a<p2.a) return true;    if(p1.a==p2.a&&p1.b<=p2.b) return true;    return false;}int main(){    int t,m = 0,n,k = 1;    scanf("%d",&t);    while(t--)    {        scanf("%d",&n);        for(int i = 0; i < n; i++)        {            scanf("%d%d",&p[i].a,&p[i].b);        }        m=0;        sort(p,p+n,cmp);        for(int i = 0; i < n; i++)        {            if(p[i].a > p[m].b)            {                m = i;                k++;            }        }        cout<<k<<endl;    }    return 0;}