Phạm vi hợp nhất trong khoảng thời gian

Question

Cho một khoảng thời gian: {1-4, 6-7, 10-12} thêm khoảng thời gian mới: (9,11) sao cho giải pháp cuối cùng được 'hợp nhất': Kết quả: {1 -4, 6-7, 9-12}. Việc sáp nhập có thể xảy ra ở cả hai bên (thấp cũng như phạm vi cao).

Tôi thấy câu hỏi này đã được trả lời ở nhiều nơi, ai đó thậm chí còn đề xuất sử dụng Interval Tress, nhưng không giải thích chính xác họ sẽ sử dụng nó như thế nào. Giải pháp duy nhất tôi biết là sắp xếp các khoảng thời gian theo thứ tự tăng dần của thời gian bắt đầu và lặp lại chúng và cố gắng hợp nhất chúng một cách thích hợp.

Nếu ai đó có thể giúp tôi hiểu cách chúng tôi có thể sử dụng cây khoảng cách trong trường hợp sử dụng này, điều đó sẽ tuyệt vời!

[Tôi đã theo cây khoảng thời gian trong CLRS cuốn sách, nhưng họ không nói về việc sáp nhập, tất cả họ nói về là chèn và tìm kiếm.]

Answer 1

(Tôi giả định rằng phương tiện này khoảng thời gian đó không bao giờ chồng lên nhau, vì nếu không chúng sẽ được hợp nhất.)

Một cách để thực hiện việc này sẽ lưu trữ cây tìm kiếm nhị phân cân bằng với một nút cho mỗi điểm cuối của một dải ô. Mỗi nút sau đó sẽ được đánh dấu là nút "mở" đánh dấu sự bắt đầu của một khoảng thời gian hoặc nút "đóng" đánh dấu sự kết thúc của một khoảng thời gian.

Khi chèn một dòng sản phẩm mới, một trong hai trường hợp sẽ xảy ra liên quan đến điểm bắt đầu của dãy:

1. Nó đã được bên trong một phạm vi, có nghĩa là bạn sẽ mở rộng một loạt đã tồn tại như một phần của việc chèn.
2. Nó không nằm trong một phạm vi, vì vậy bạn sẽ tạo một nút "mở" mới.

Để xác định trường hợp bạn đang ở, bạn có thể thực hiện tìm kiếm tiền thân trong cây cho điểm bắt đầu của phạm vi. Nếu bạn nhận được NULL hoặc nút đóng, bạn cần chèn một nút mở mới biểu thị điểm bắt đầu của dải ô. Nếu bạn nhận được một nút mở, bạn sẽ chỉ tiếp tục mở rộng khoảng thời gian đó.

Từ đó, bạn cần phải xác định phạm vi mở rộng bao xa. Để thực hiện việc này, hãy liên tục tính toán người kế thừa của nút ban đầu mà bạn đã chèn cho đến khi một trong những điều sau xảy ra:

1. Bạn đã xem tất cả các nút trong cây. Trong trường hợp đó, bạn cần phải chèn một nút đóng đánh dấu sự kết thúc của khoảng thời gian này.

2. Bạn thấy nút đóng sau khi kết thúc phạm vi. Trong trường hợp đó, bạn đang ở giữa phạm vi hiện có khi phạm vi mới kết thúc, vì vậy bạn không cần phải làm gì thêm. Bạn đã hoàn tất.

3. Bạn thấy nút đóng hoặc mở trước khi kết thúc phạm vi. Trong trường hợp đó, bạn cần phải loại bỏ nút đó khỏi cây, vì phạm vi cũ được gộp bởi một dãy mới.

4. Bạn thấy nút mở sau khi kết thúc phạm vi. Trong trường hợp đó, chèn một nút đóng mới vào cây, vì bạn cần phải kết thúc phạm vi hiện tại trước khi nhìn thấy sự bắt đầu của cái mới này.

thực hiện ngây thơ, thời gian chạy của thuật toán này là O (log n + k log n), trong đó n là số khoảng cách và k là số khoảng cách loại bỏ trong quá trình này (vì bạn phải làm n xóa). Tuy nhiên, bạn có thể tăng tốc độ này lên O (log n) bằng cách sử dụng thủ thuật sau đây. Vì quá trình xóa luôn xóa các nút trong một chuỗi, bạn có thể sử dụng tìm kiếm kế thừa cho điểm cuối để xác định kết thúc phạm vi cần xóa. Sau đó, bạn có thể ghép các subrange để loại bỏ ra khỏi cây bằng cách thực hiện hai hoạt động tách cây và một hoạt động nối cây. Trên một cây cân bằng thích hợp (màu đỏ-đen hoặc splay, ví dụ), điều này có thể được thực hiện trong tổng thời gian O (log n), nhanh hơn rất nhiều nếu có rất nhiều dãy được sắp xếp.

Hy vọng điều này sẽ hữu ích!

Answer 2

Kiểm tra này ra. Nó có thể giúp bạn: - http://www.boost.org/doc/libs/1_46_0/libs/icl/doc/html/index.html

Thư viện cung cấp các chức năng:

1) interval_set

2) separate_interval_set

3) split_interval_set

Answer 3

Việc này đơn giản được thực hiện bằng cách thêm khoảng thời gian được đề cập vào cuối bộ khoảng thời gian, sau đó thực hiện hợp nhất trên tất cả các phần tử của bộ khoảng thời gian.

Các hoạt động hợp nhất nổi chi tiết tại đây: http://www.geeksforgeeks.org/merging-intervals/

Nếu bạn không có tâm trạng cho C++, đây là những điều tương tự trong python:

def mergeIntervals(self, intervalSet): 
    # interval set is an array. 
    # each interval is a dict w/ keys: startTime, endTime. 
    # algorithm from: http://www.geeksforgeeks.org/merging-intervals/ 
    import copy 
    intArray = copy.copy(intervalSet) 
    if len(intArray) <= 1: 
     return intArray 
    intArray.sort(key=lambda x: x.get('startTime')) 
    print "sorted array: %s" % (intArray) 
    myStack = [] #append and pop. 
    myStack.append(intArray[0]) 
    for i in range(1, len(intArray)): 
     top = myStack[0] 
     # if current interval NOT overlapping with stack top, push it on. 
     if (top['endTime'] < intArray[i]['startTime']): 
      myStack.append(intArray[i]) 
     # otherwise, if end of current is more, update top's endTime 
     elif (top['endTime'] < intArray[i]['endTime']): 
      top['endTime'] = intArray[i]['endTime'] 
      myStack.pop() 
      myStack.append(top) 

    print "merged array: %s" % (myStack) 
    return myStack 

Đừng quên bạn nosetests để xác minh bạn thực sự đã làm công việc đúng:

class TestMyStuff(unittest.TestCase): 

    def test_mergeIntervals(self): 
     t = [ { 'startTime' : 33, 'endTime' : 35 }, { 'startTime' : 11, 'endTime' : 15 }, { 'startTime' : 72, 'endTime' : 76 }, { 'startTime' : 44, 'endTime' : 46 } ] 
     mgs = MyClassWithMergeIntervalsMethod() 
     res = mgs.mergeIntervals(t) 
     assert res == [ { 'startTime' : 11, 'endTime' : 15 }, { 'startTime' : 33, 'endTime' : 35 }, { 'startTime' : 44, 'endTime' : 46 }, { 'startTime' : 72, 'endTime' : 76 } ] 

     t = [ { 'startTime' : 33, 'endTime' : 36 }, { 'startTime' : 11, 'endTime' : 35 }, { 'startTime' : 72, 'endTime' : 76 }, { 'startTime' : 44, 'endTime' : 46 } ] 
     mgs = MyClassWithMergeIntervalsMethod() 
     res = mgs.mergeIntervals(t) 
     assert res == [{'endTime': 36, 'startTime': 11}, {'endTime': 46, 'startTime': 44}, {'endTime': 76, 'startTime': 72}] 

Answer 4

công MergeIntervals lớp {

public static class Interval { 

    public double start; 
    public double end; 

    public Interval(double start, double end){ 
     this.start = start; 
     this.end = end; 
    } 
} 

public static List<Interval> mergeInteval(List<Interval> nonOverlapInt, Interval another){ 

    List<Interval> merge = new ArrayList<>(); 

    for (Interval current : nonOverlapInt){ 

     if(current.end < another.start || another.end < current.start){ 
      merge.add(current); 
     } 
     else{ 

      another.start = current.start < another.start ? current.start : another.start ; 
      another.end = current.end < another.end ? another.end : current.end;     
     }   
    } 
    merge.add(another); 
    return merge; 
} 

Answer 5

C#

public class Interval 
{ 
    public Interval(int start, int end) { this.start = start; this.end = end; } 
    public int start; 
    public int end; 
} 

void AddInterval(List<Interval> list, Interval interval) 
{ 
    int lo = 0; 
    int hi = 0; 
    for (lo = 0; lo < list.Count; lo++) 
    { 
     if (interval.start < list[lo].start) 
     { 
      list.Insert(lo, interval); 
      hi++; 
      break; 
     } 
     if (interval.start >= list[lo].start && interval.start <= list[lo].end) 
     { 
      break; 
     } 
    } 
    if (lo == list.Count) 
    { 
     list.Add(interval); 
     return; 
    } 

    for (hi = hi + lo; hi < list.Count; hi++) 
    { 
     if (interval.end < list[hi].start) 
     { 
      hi--; 
      break; 
     } 
     if (interval.end >= list[hi].start && interval.end <= list[hi].end) 
     { 
      break; 
     } 
    } 
    if (hi == list.Count) 
    { 
     hi = list.Count - 1; 
    } 

    list[lo].start = Math.Min(interval.start, list[lo].start); 
    list[lo].end = Math.Max(interval.end, list[hi].end); 

    if (hi - lo > 0) 
    { 
     list.RemoveRange(lo + 1, hi - lo); 
    } 
}