간격 집합의 최대 깊이 찾기

Question

간격 집합 I가 주어지면 [a_i, b_i] 형식의 각 요소가 최대 깊이의 끝점 b_i를 O (n * logn) 시간으로 찾습니다. 점 깊이가 "찌르기"(또는 교차)하는 간격의 수로 x의 깊이를 정의하십시오. 두 끝점의 깊이가 같으면 작은 쪽을 반환합니다.

---

시도 :

나는 방법 O에 (N * logn) 시간을 찾을 수 모른다. 간격 집합의 찌르는 집합을 찾는 욕심 많은 알고리즘을 이해하지만 엄격하게 O (n * log n) 시간을 가진 끝점을 찾는 것은 매우 다른 것처럼 보입니다.

우선 간격을 지정하고 최대 심도 끝점을 지정할 수 있지만 O (n * log n) 시간을 보장 할 수는 없습니다.

Answer 1

다음과 같은 시도 할 수 있습니다 : 당신이 (에 "A"지점이 발생할 때 포인트 A_I 및 b_i

가 정렬 된 배열이 카운터 (깊이)를 증가 통과 (함께 하나 개의 배열)

• 종류 간격을 시작) "b"지점 (간격의 끝)에 대한 감소 - 최대 깊이와 함께 "b"지점을 찾을 수 있습니다