点击打开链接

lines

Time Limit: 5000/2500 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 453 Accepted Submission(s): 220

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

Sample Output

3
1

Source BestCoder Round #20

官方题解：

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

//953MS	1792K
#include
  
   
#include
   
     using namespace std; pair
    
     p[200007]; int main() { int t; scanf("%d",&t); while(t--) { int n,a,b; scanf("%d",&n); for(int i=0;i
     
      maxx)maxx=ans; } printf("%d\n",maxx); } return 0; }

HDU 5124 lines 最多区间覆盖

lines