분리 된 간격의 정렬 된 목록에 간격 삽입

Question

나는 분리 된 간격 및 간격의 정렬 된 목록을가집니다. [(1, 5), (10, 15), (20, 25)] 및 (12, 27). 그래서, (12,27)은 간격입니다. [(1, 5), (10, 27)]와 같은 분리 된 간격의 정렬 된 목록으로 병합하려고합니다.

Answer 1

의사 : 당신은 실제로 당신의 간격이 노드이며, 그들이 공통 부분 (예를 들어 (12,27)가 연결되어있는 경우들이 서로 연결되어에서, 그래프 문제를 모델링 할 수

list = ... 
u = (12,27) 
i = 0 
newlist = [] 

while (max(list[i]) < min(u)) //add all intervals before intersection 
    newlist.add(list[i++]) 
mini = i 

while (min(list[i]) < max(u)) // skip all intersecting intervals 
    i++ 
maxi = i 

newlist.add((min(list[mini],u),max(list[maxi],u)) // add the new interval 

while (i < list.length) // add remaining intervals 
    newlist.add(list[i++]) 

return newlist 

Answer 2

(15, 20))은 이제 제는 각 연결 컴포넌트에 시작 (예 10) 및 단부 의 최대 값 (예 : 25)의 최소값을 찾아 연결 컴포넌트를 찾을 것이다. Interval Graphs을 참조하는 것이 좋습니다.

Answer 3

여기에 vars로 가득 찬 비 관용적 인 스칼라 솔루션이 있습니다. 솔루션은 필자가해야 할 것보다 길어 보입니다. 왜냐하면 필자가 부가 작업만을 지원하는 목록에 추가 및 삽입을 수행하지 못하기 때문입니다.

1. 스캔 새로운 간격 할 것들과 겹치지 않는 두리스트 것들에 간격 목록을 나누어 다음과 같이

   ALGO이다. 겹치지 않는 간격은 새로운 간격 이후 또는 완전히 시작하기 전에 시작하는 간격입니다. 또한 우리가 새로운 간격을 삽입한다면, 그것보다 낮은 가장 높은 간격 이후에있을 것입니다. 이 단계에서 우리는 겹치는 간격 목록과 겹치지 않는 목록 목록을 가지고 있습니다.

2. 중복이없는 경우 새 간격은 모든 주어진 간격보다 빠르거나 모든 간격 이후 또는 두 간격 사이에서 (여전히 겹치지 않음) 발생합니다.
3. 중복되는 경우 새 간격으로 겹치는 간격을 병합하십시오. 겹치는 간격의 시작은 min (새 간격 시작, 가장 작은 겹침 간격 시작)입니다. 우리는 비슷하게 끝을 계산할 수 있습니다. 이제 이전에 계산 된 위치에 겹치는 간격을 삽입하십시오.

   object trial { 
       val intervals1 = List((1, 2), (4, 6), (7, 8), (16, 17))) 
       val intervals2 = List((1, 5), (10, 15), (20, 25) 
   
       val newInterval1 = (11, 12) 
       val newInterval2 = (12, 27) 
   
       // Interval algo test. 
       val result1 = Merge(intervals1, newInterval1) // result1 : List((1,2), (4,6), (7,8), (11,12), (16,17)) 
       val result2 = Merge(intervals2, newInterval2) // result2 : List[(Int, Int)] = List((1,5), (10,27)) 
       } 
   
   object Merge{ 
       def append[T](list: List[T], el: T): List[T] = { 
       (el :: list.reverse).reverse 
       } 
       def insert[T](list: List[T], pos: Int, elem: T): List[T] = { 
       var newList = List.empty[T] 
       val reversePos = list.length - pos 
       list.reverse.zipWithIndex foreach { 
        case(el, i) if i == reversePos => { 
        newList = elem :: newList 
        newList = el :: newList 
        } 
        case (el, i) => newList = el :: newList 
       } 
       newList 
       } 
   
       def apply(list: List[(Int, Int)], interval: (Int, Int)): List[(Int, Int)] = { 
       val (min, max) = interval 
       var newList = List.empty[(Int, Int)] 
       // Store potentially overlapping stuff. 
       var overlap = List.empty[(Int, Int)] 
       // Maintain the position to begin merge. 
       var posInsert = 0 
       list.zipWithIndex foreach { case(intervalz, i) => 
        if (intervalz._2 < min) { 
        // Does not overlap but an insert will be after the highest of these. 
        posInsert = i 
        newList = append(newList, intervalz) 
        } else if (intervalz._1 > max) { 
        // Does not overlap. 
        newList = append(newList, intervalz) 
        } else overlap = append(overlap, intervalz) 
       } 
       if (overlap isEmpty) { 
        if (posInsert == 0) newList = interval :: newList 
        else newList = insert(newList, posInsert + 1, interval) 
       } else { 
        // Start of new interval is the lower of the first overlap's start or the interval's start. 
        val startOfInterval = Math.min(overlap.head._1, min) 
        // Enf of interval is higher of last overlap's end or interval's end. 
        val endOfInterval = Math.max(overlap.head._2, max) 
        // Insert the merged interval after the highest interval smaller than the start of the new internval. 
        if (posInsert == 0) newList = (startOfInterval, endOfInterval) :: newList 
        else newList = insert(newList, posInsert + 1, (startOfInterval, endOfInterval)) 
       } 
       newList 
       } 
   } 
   

   그것은 여기에 언급 된 시험을 통과하고, O (N)이다 : 여기

코드이다.

EDIT. 알곤 버전 :

intervals = [....] 
newInterval = (12, 27) 
newList = [] 
overlappingList = [] 
posInsert = 0 
i = 0 

while (i < intervals.size) 
    if (intervals[i].max < newInterval.min) 
    posInsert = i 
    append(newList, intervals[i]) 
    else if (intervals[i].min > newInterval.max) 
    append(newList, intervals[i]) 
    else 
    append(overlappingList, intervals[i]) 
    i++ 

if (overlap isEmpty) 
    if (posInsert == 0) prepend(newList, newInterval) 
    else insert(newList, posInsert + 1, newInterval) 
else 
    start = Min(overlappingList[i].min, newInterval.min) 
    end = Max(overlappingList[i].max, newInterval.max) 
    if (posInsert == 0) prepend(newList, newInterval) 
    else insert(newList, posInsert + 1, new Interval(start, end)) 
return newList