我用了快排，但提交后还是超时了，请问有更好的解决方法吗？

题目如下：



代码如下：
#include<stdio.h>
#include<stdlib.h>

int a[1000000];

int cmp(const void*a,const void*b)
{
return *(int*)a-*(int*)b;
}

int main()
{
    int T,n,k,i,t,x,y,temp;

    scanf("%d",&T);

    while(T--)
    {
        scanf("%d%d",&n,&k);

        for(i=0; i<n; i++)
            a[i]=0;

        for(i=1; i<=k; i++)
        {
            scanf("%d%d",&x,&y);
            for(t=x-1; t<=y-1; t++)
                a[t]++;
        }

        qsort(a,n,sizeof(int),cmp);

        printf("%d\n",a[n/2]);

    }

    return 0;
}