lines

Time Limit: 5000/2500 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 1350    Accepted Submission(s): 558

Problem 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 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.

 

 

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

 

给你n条线段（点也算线段），让你找出被覆盖次数最多的线段的覆盖次数。

直接从左往右跑，线段起点加一过了减一。。。

官方题解：

我们可以将一条线段[xi,yi]分为两个端点xi和(yi)+1， 在xi时该点会新加入一条线段，同样的，在(yi)+1时该点会减少一条线段， 因此对于2n个端点进行排序，令xi为价值1，yi为价值-1，问题转化成了最大区间和， 因为1一定在-1之前，因此问题变成最大前缀和，我们寻找最大值就是答案，另外的， 这题可以用离散化后线段树来做。复杂度为排序的复杂度即nlgn， 另外如果用第一种做法数组应是2n，而不是n，由于各种非确定性因素我在小数据就已 经设了n=10W的点。

题解：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #define mem(x,y) memset(x,y,sizeof(x)) 7 using namespace std; 8 typedef long long LL; 9 const int INF=0x3f3f3f3f;10 const int MAXN=1e5+100;11 pair
           
            pa[MAXN<<1];12 int main(){13 int T,N;14 scanf("%d",&T);15 while(T--){ int a,b;16 scanf("%d",&N);17 for(int i=0;i