빠른 방법 카운트 간격 배열의 오버랩 간격 수?

Question

좋아, 이건 내가 진보 된 알고리즘 클래스에 대해 가지고있는 질문이다. 나는 이미 한 번 솔루션을 돌렸지 만, 효율성 문제로 인해 강사가 거부했기 때문에 이미 내 노력을 기울 였지만 힌트를 얻은 후에도 이해할 수 없었으므로 부드럽게 다루어주십시오. 나는 그의 힌트를 아래에 줄 것이다

출발점과 종점이 둘 다있는 간격의 배열이 주어지면 각 간격마다 다른 간격의 수를 찾으십시오. 간격의 수는 10^9보다 작으며 ID는 고유합니다. 시작과 끝이 10^18보다 작 으면 입력 파일에 시작과 끝의 중복 번호가 포함되지 않습니다. 위의 모든 숫자는 정수입니다.

힌트 : 버킷이있는 데이터 구조 고려. 이 알고리즘은 O보다 회 (N^2) 숫자는 꽤 크고

sample input and output 

input: 
5 %% number of intervals 
2 100 200 %% id, start,end. all lines below follows this 
3 110 190 
4 105 145 
1 90 150 
5 102 198 

output: 
3 0 
4 0 
1 1 
5 2 
2 3 

Answer 1

그래서 O는 (N N 로그) 정도에 약간있을 수 있지만 여기에 생각이 빠르게해야한다.

먼저 값을 정규화합니다. 즉, 동일한 순서를 유지하면서 값을 작게 만듭니다.

5 
2 2 10 
3 5 8 
4 4 6 
1 1 7 
5 3 9 

지금 간격의 가장자리 [1, 2 N]의 범위에있다 : 당신의 예에서 정상화는

90 100 102 105 110 145 150 190 198 200 
    1 2 3 4 5 6 7 8 9 10 

그래서 새로운 간격이있어 할 것이다.

이제 자신의 말에 간격을 분류 :

5 
4 4 6 
1 1 7 
3 5 8 
5 3 9 
2 2 10 

당신이 아직 전에 시작하고 발생되지 않은 모든 간격이 그들의 대답은 하나 증가한다고 말할 수있는 간격에 도달

. 이 작업은 SegmentTree를 사용하여 수행 할 수 있습니다.

간격 [x, y]를 얻었을 때 [1, x - 1] 범위의 모든 값을 1 씩 증가시킨 다음 세그먼트 트리에서 x의 값으로 해답을 계산합니다. 이것은 간격과 쿼리에 추가 된 것으로 일반적인 세그먼트 트리 문제입니다.

O (N log N) 시간 및 O (N) 메모리 미만으로이 문제를 해결할 수 있다고 생각하지 않습니다. 따라서이 솔루션은 시간과 공간 모두에서 점근 적으로 최상의 솔루션이어야합니다.