Time Limit: 2500MS Memory Limit: 32768KB 64bit IO Format: %I64d & %I64u

Description

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.

Input

The first line contains a single in$T(1 \leq T \leq 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 \leq N \leq 10^5)$,indicating the number of lines.
Next N lines contains two integers $X_i$ and $Y_i(1 \leq X_i \leq Y_i \leq 10^9)$,describing a line.

Output

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

Sample Input

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

Sample Output

3
1

Source

PS：貌似能用贪心做
AC代码：
#include <algorithm>
#include <cstring>
#include <cstdio>

#define lson id << 1, l, mid
#define rson id << 1 | 1, mid + 1, r

using namespace std;
int n;
const int maxn = 100000 + 10;
int a[maxn * 2], L[maxn], R[maxn];
struct node
{
int l, r, lazy, max;
}tree[maxn * 8];
void input()
{
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d%d", &L[i], &R[i]);
}
void build(int id, int l, int r)
{
tree[id].l = l, tree[id].r = r, tree[id].lazy = tree[id].max = 0;
if (l == r)
return;
int mid = (l + r) >> 1;
build(lson);
build(rson);
}
void pushdown(int id)
{
if (tree[id].lazy)
{
tree[id << 1].lazy += tree[id].lazy;
tree[id << 1].max += tree[id].lazy;
tree[id << 1 | 1].lazy += tree[id].lazy;
tree[id << 1 | 1].max += tree[id].lazy;
tree[id].lazy = 0;
}
}
void update(int id, int l, int r)
{
if (tree[id].l == l && tree[id].r == r)
{
tree[id].lazy++;
tree[id].max++;
return;
}
pushdown(id);
int mid = (tree[id].l + tree[id].r) >> 1;
if (r <= mid)
update(id << 1, l, r);
else if (l > mid)
update(id << 1 | 1, l, r);
else
{
update(lson);
update(rson);
}
tree[id].max = max(tree[id << 1].max, tree[id << 1 | 1].max);
}
void solve()
{
for (int i = 0; i < n; i++)
{
a[i] = L[i];
a[i + n] = R[i];
}
sort(a, a + 2 * n);
int cnt = 1;
for (int i = 1; i < 2 * n; i++)
if (a[i] != a[i - 1])
a[cnt++] = a[i];
build(1, 1, cnt);
for (int i = 0; i < n; i++)
{
int l = lower_bound(a, a + cnt, L[i]) - a + 1,
r = lower_bound(a, a + cnt, R[i]) - a + 1;
//cout << l << ' ' << r << endl;
update(1, l, r);
}
printf("%d\n", tree[1].max);
}
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
input();
solve();
}
return 0;
}