HDU 5124 lines 最多區間覆蓋

點擊打開鏈接

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

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 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;
pairp[200007];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,a,b;
        scanf("%d",&n);
        for(int i=0;imaxx)maxx=ans;
        }
        printf("%d\n",maxx);
    }
    return 0;
}