숫자 라인에서 선분의 합집합을 찾는다

Question

나는 0에서 1000 사이의 숫자 라인을 가지고있다. 나는 숫자 라인에 많은 선분을 가지고있다. 모든 선분 'x1은> = 0이고 모든 x2는 <000입니다. 모든 x1과 x2는 정수입니다.

모든 선분의 조합을 찾아야합니다.

이 이미지에서

, 선분은 파란색이며, 노동 조합은 빨간색입니다 :이 유형의 문제에 대한 기존 알고리즘

있습니까?

Answer 1

marzullo의 알고리즘을 사용할 수 있습니다 (자세한 내용은 Wikipedia 참조).

def ip_ranges_grouping(range_lst): 
    ## Based on Marzullo's algorithm 
    ## Input: list of IP ranges 
    ## Returns a new merged list of IP ranges 
    table = [] 
    for rng in range_lst: 
     start,end = rng.split('-') 
     table.append((ip2int(start),1)) 
     table.append((ip2int(end),-1)) 
    table.sort(key=lambda x: x[0]) 
    for i in range(len(table) - 1): 
     if((table[i][0] == table[i+1][0]) and ((table[i][1] == -1) and (table[i+1][1] == 1))): 
      table[i],table[i+1] = table[i+1],table[i] 

    merged = [] 
    end = count = 0 
    while (end < len(table)): 
     start = end 
     count += table[end][1] 
     while(count > 0): # upon last index, count == 0 and loop terminates 
      end += 1 
      count += table[end][1] 
     merged.append(int2ip(table[start][0]) + '-' + int2ip(table[end][0])) 
     end += 1 
    return merged 

Answer 2

세그먼트가 동적으로 변경되지 않으면 간단한 문제입니다. 그때 정렬 요소를 스캐닝 좌단 모든 세그먼트를 분류 :

struct Seg {int L,R;}; 

int cmp(Seg a, Seg b) {return a.L < b.L;} 

int union_segs(int n, Seg *segs, Segs *output) { 
    sort(segs, segs + n, cmp); 
    int right_most = -1; 
    int cnt = 0; 
    for (int i = 0 ; i < n ; i++) { 
    if (segs[i].L > right_most) { 
     right_most = segs[i].R; 
     ++cnt; 
     output[cnt].L = segs[i].L; 
     output[cnt].R = segs[i].R; 
    } 
    if (segs[i].R > right_most) { 
     right_most = segs[i].R; 
     output[cnt].R = segs[i].R; 
    } 
    } 
    return cnt+1; 
} 

시간 복잡도는 O (nlogn) (정렬)는 + O (N) (주사).

세그먼트를 동적으로 삽입 및 삭제하고 언제든지 유니언을 쿼리하려면 range tree과 같은 좀 더 복잡한 데이터 구조가 필요합니다.

Answer 3

세그먼트의 좌표가 경계가있는 ([0, 1000]) 정수라고 생각하면 0으로 초기화 된 크기가 1000 인 배열을 사용할 수 있습니다. 그런 다음 세그먼트 세트를 실행하고 세그먼트에서 다루는 배열의 모든 셀에 1을 설정하십시오. 당신 만 복잡 세그먼트의 수에 따라 달라집니다뿐만 아니라 자신의 길이에 1

---  ----- 
    --- --- 
1111100111111100 

의 인접하게 순서를 확인하기 위해 배열을 실행해야합니다.

또 다른 방법은 부동 소수점 세그먼트에서도 사용할 수 있습니다. 세그먼트를 정렬하십시오. 그런 다음 정렬 된 세그먼트를 이동하고 각 인접한 세그먼트의 경계를 비교하면됩니다. 그들이 교차하면, 그들은 같은 조합에 속해 있습니다.