bestcoder lines

  
John has several lines. The lines are covered on the X axis. Let A is a point which is covered by the most lines. John wants to know how many lines cover A.

  
The first line contains a single integer T(1≤T≤100)(the data for N>100 less than 11 cases),indicating the number of test cases.
Each test case begins with an integer N(1≤N≤105),indicating the number of lines.
Next N lines contains two integers Xi and Yi(1≤Xi≤Yi≤109),describing a line. 

  
For each case, output an integer means how many lines cover A.

  
2
5
1 2 
2 2
2 4
3 4
5 1000
5
1 1
2 2
3 3
4 4
5 5

  
3
1
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <algorithm>
using namespace std;const double EPS=1e-8;
const int MAXN=1000000+5;
int a[MAXN*2], b[MAXN*2];struct node
{int star, en;
} len[MAXN];int bs(int a[], int l, int r, int x)
{int mid = (l+r) / 2;while(a[mid] != x){if(a[mid] > x) {r = mid;}else if(a[mid] < x) {l = mid;}mid = (l+r)/2;}return mid;
}
int main()
{int cases, n, i;scanf("%d", &cases);while(cases--){int cnt = 0, maxx = 0;memset(a, 0, sizeof(a));memset(b, 0, sizeof(b));scanf("%d", &n);for(i = 0; i < n; i++){scanf("%d %d", &len[i].star, &len[i].en);a[cnt++] = len[i].star;a[cnt++] = len[i].en;}sort(a, a+cnt);int p = 1;for(i = 1; i < cnt; i++){if(a[i] != a[i-1])a[p++] = a[i];}cnt = p;for(i = 0; i < n; i++){int mid = bs(a, 0, cnt, len[i].star);b[mid] += 1;mid = bs(a, 0, cnt, len[i].en);b[mid+1] += -1;}int ans = b[0];for(i = 1; i < cnt; i++){b[i] = b[i-1]+b[i];if(b[i] > ans)ans = b[i];}printf("%d\n", ans);}return 0;
}