중첩되는 집합의 간격 찾기

Question

그래서 간격의 끝점을 포함하는 집합이 있습니다. 예 :

Set s = {(1,4),(3,7),(5,8),(14,17),(0,2),(11,14)} 

얼마나 많은 겹치는 간격이 있는지 알아야합니다. 위의 경우, 대답은 내가 합계를 찾아 O(N log N) 시간이 걸리는 알고리즘을 필요로 5

(1,4) --> (3,7), (0,2) 
(3,7) --> (5,8),(0,2) 
(5,8) --> 
(14,17) --> (11,14) 

이후가 될 것입니다. 이제 모든 시작점을 정렬하고 여기에 제시된 답변을 모든 점 Find number range intersection에 적용하면 O (N^2) 솔루션을 얻게됩니다. 세트 이외에 어떤 종류의 데이터 구조가 필요할 지에 대한 단서가 있습니까? 감사!

Answer 1

모든 간격 [a, b]에 대해 값 목록 (a, -1), (b, 1)을 작성하십시오. 이제 이들을 정렬하여 배열을 통과하면서 +1과 -1을 집계하여 각 끝점에서 현재 열려있는 간격의 수를 계산할 수 있습니다.

(b, 1)은 정렬 된 목록에서 (b, -1) 뒤에 오는 것이 중요합니다. 교차점이 단일 지점에 있더라도 교차점을 계산하기를 원하기 때문입니다.

여기에 전체 코드가 나와 있습니다.

def overlaps(intervals): 
    es = [] 
    for a, b in intervals: 
     es.append((a, -1)) 
     es.append((b, 1)) 
    es.sort() 
    result = 0 
    n = 0 
    for a, s in es: 
     if s == -1: result += n 
     n -= s 
    return result 

참고로, 이는 거의 O (n log n)이며, 멋진 데이터 구조는 필요하지 않습니다.

Answer 2

먼저 (0,1)과 (1,2)이 겹치는 것으로 가정합니다.

, BTW 당신의 예는 (3,7)이게 해결하기 위해 (0,2)

한 가지 방법으로 겹치지 않는, 잘못된 : 시작점 가장 낮은 시작 지점에서

으로 반복을 기반으로

1. 정렬 간격 가장 높은 지점까지
   2a. 현재 시작점보다 큰 이전 종점의 수를 또는으로 계산하십시오.
   2b. 현재 종점 계산에 하나를 더하십시오.

1 단계는 상기 카운트를하는 동안 2 모든 구간 반복된다 O(n log n)
단계에서 수행 될 수있다. 따라서 O(n * X)입니다. 여기서 X은 계산을 수행하는 복잡성입니다. Fenwick Tree을 사용하면 O(log n) 에서 할 수 있으므로 단계 2는 O(n log n)에서도 완료 할 수 있습니다.

따라서 전체적인 복잡도는 O(n log n)입니다.

의사 코드 :

def fenwick_tree.get(num): 
    return the sum from counter[0] to counter[num] 

def fenwick_tree.add(num, val): 
    add one to counter[num] 

intervals = [...] 
sort(intervals) # using the starting point as the key 
init_fenwick_tree() 
sum = 0 
count = 0 
for (starting_point, end_point) in intervals: 
    sum = sum + (count - fenwick_tree.get(starting_point-1)) 
    fenwick_tree.add(end_point,1) 
return sum 

파이썬 코드 (간격 점은 음이 아닌 정수 경우에만 작동) :

MAX_VALUE = 2**20-1 
f_arr = [0]*MAX_VALUE 

def reset(): 
    global f_arr, MAX_VALUE 
    f_arr[:] = [0]*MAX_VALUE 

def update(idx,val): 
    global f_arr 
    while idx<MAX_VALUE: 
     f_arr[idx]+=val 
     idx += (idx & -idx) 

def read(idx): 
    global f_arr 
    if idx <= 0: 
     return 0 
    result = 0 
    while idx > 0: 
     result += f_arr[idx] 
     idx -= (idx & -idx) 
    return result 

intervals = [(1,4),(3,7),(5,8),(14,17),(0,2),(11,14)] 
intervals = sorted(intervals, key=lambda x: x[0]) 
reset() 
total = 0 
for processed, interval in enumerate(intervals): 
    (start, end) = interval 
    total += processed - read(start-1) 
    update(end, 1) 
print total 

는 4 인쇄됩니다, 이러한 중복에서 오는 :

 
(0,2) - (1,4) 
(1,4) - (3,7) 
(3,7) - (5,8) 
(11,14) - (14,17) 

겹치는 간격을 얻을 수 없다는 점에 유의하십시오. 최악의 경우 다시 O(n^2) 중복됩니다, O(n log n) 시간에 인쇄 할 수 없습니다.

실제로

¹ _{펜윅 트리 M이 구간에서 고유 값의 최대 가능 수이다 O(log M) 시간의 계산을한다. 많은 다른 값이있을 수 있기 때문에 M <= 2n에 유의하십시오. Fenwick Tree가 O(log n) 시간에 카운팅을한다고 말하는 것도 맞습니다.}

Answer 3

빠른 아이디어 : 우선 간격을 정렬하십시오. 이제 간격을두고 엔드 포인트별로 정렬 된 최소 힙에 각각 추가하십시오. 각 간격마다 해당 간격의 시작 지점보다 작은 모든 항목을 힙에서 제거하십시오. 힙에 남아있는 모든 엔드 포인트는이 간격 이전에 시작하여 겹치는 간격을 나타내므로 overlaps을 힙 크기만큼 증가시킵니다. 이제 현재 간격을 힙에 추가하고 계속하십시오.

의사에

:

Sort(intervals) 
(firstStart, firstEnd) = intervals[0] 
currentIntervals = MinHeap() 
overlaps = 0 

for each (start, end) in intervals[1:]: 
    remove from currentIntervals all numbers < start 
    overlaps += Size(currentIntervals) 
    HeapPush(end, currentIntervals) 
return overlaps 

나는이 테스트를하지 않은,하지만 적어도 그럴듯하게 보인다.

Answer 4

이것은 Greedy 기술을 사용하여 간단히 수행 할 수 있습니다. 은 다음 단계를 수행 낮은 시점에서 최고점 에 시작점 대하여 반복에 기초

정렬 간격의 현재 시점보다 크거나 같은 앞의 엔드 포인트의 수를 카운트. 현재 끝점의 수를 증가시킵니다.

Answer 5

폴의 대답은 정말 똑똑합니다. 인터뷰면 그 아이디어가 떠오르지 않는다고 생각합니다. 여기에는 또 다른 버전 인 O (nlog (n))도 있습니다.

import heapq 

def countIntervals(s): 
    s.sort() 
    end = [s[0][1]] 
    res, cur = 0, 0 
    for l in s[1:]: 
     if l[0]>heapq.nsmallest(1, end)[0]: 
      heapq.heappop(end) 
     cur = len(end) 
     res += cur 
     end.append(l[1]) 
    return res 

향후 엔드 포인트를 저장하는 최소 힙을 유지합니다. 새로운 간격이 생길 때마다 우리는 지금까지 시작점과 가장 작은 끝점을 비교해야합니다.

시작점이 클 경우 가장 큰 끝점 (해당 간격을 나타냄)이 중복을 더 이상 발생시키지 않음을 의미합니다. 그러므로 우리는 그것을 밖으로 나옵니다.

시작 지점이 더 작 으면 모든 종료 지점 (해당 간격)이 새로운 간격과 겹치고 있음을 의미합니다.

그런 다음 종점 ("cur")의 수는이 새로운 새로운 간격으로 가져 오는 겹치는 수입니다. 결과를 업데이트 한 후에는 새로운 간격의 끝점을 힙에 추가합니다.