Computer Arrangement

Time Limit:1000MS  Memory Limit:65536K
Total Submit:451 Accepted:106

Description

每年新学期，计算中心的老师都要安排上机时间。
现设有n个班级E={1, 2, 3, ..., n}, 要使用8号机房，同一时间内只允许一个班级使用该机房。设班级i上机的起止时间区间为[si,fi),如果班级i使用了8号机房, 则它在时间[si,fi)内占用该机房，若区间[si,fi)和[sj,fj)不相交，则称班级i和j均可安排上机的。现在要求你安排一下上机情况，使尽可能多的班级能有机会上机。

Input

有多组测试数据。
第1行先输入整数t(1<= t <= 100),表示共有t组测试数据。
每组测试数据输入共有3行，
第1行为一个整数n(1 <＝ n <＝ 100) 表示班级数
第2行共n个整数，为这n个班级希望上机的开始时间(以某一时间为基准）
第3行共n个整数，为这n个班级上机的终止时间

Output

对于每个测试案例输出最多可以安排上机的班级

Sample Input


1
11
1 3 0 5 3 5 6 8 8 2 12
4 5 6 7 8 9 10 11 12 13 14

Sample Output


4

Source

yhr





#include<stdio.h>
main()
{
    int t,n;
    int min1,min2,str[100],num[100];
    int i,j,k,g;
    while(scanf("%d",&t)!=EOF)
    {
        scanf("%d",&n);
        for(i=1;i<=n;i++)
        {
            scanf("%d",&str[i]);
        }
        for(i=1;i<=n;i++)
        {
            scanf("%d",&num[i]);
        }
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n-1-i;j++)
            {
                if(num[j]>num[j+1])
                {
                    min1=str[j];
                    str[j]=str[j+1];
                    str[j+1]=min1;
                    
                    min2=num[j];
                    num[j]=num[j+1];
                    num[j+1]=min2;
                }
            }
        }
        k=1;
        j=1;
        for(i=k+1;i<=n;i++)
        {
            if(str[i]>=num[k])
            {
                k=i;
                j++;
            }
        }
        printf("%d\n",j);
    }
}