Làm thế nào để chức năng merge chồng chéo số-dao động từ một danh sách

Question

Tôi có một số phạm vi-đối tượng mà tôi cần phải hợp nhất để tất cả các dãy chồng chéo biến mất:

case class Range(from:Int, to:Int) 

val rangelist = List(Range(3, 40), Range(1, 45), Range(2, 50), etc) 

Dưới đây là các dãy:

3 40 
    1 45 
    2 50 
70 75 
75 90 
80 85 
100 200 

Sau khi hoàn tất, chúng tôi sẽ nhận được:

1 50 
70 90 
100 200 

Imperative Thuật toán:

0.123.

1. Pop() dải ô đầu tiên và lặp lại thông qua phần còn lại của danh sách so sánh nó với mỗi dải khác.
2. nếu có mục chồng chéo, hợp nhất chúng lại với nhau (Điều này mang lại một trường hợp Phạm vi mới) và xóa 2 ứng viên hợp nhất khỏi danh sách nguồn.
3. Ở cuối danh sách, thêm đối tượng Phạm vi (có thể thay đổi nhiều lần thông qua hợp nhất) thành danh sách kết quả cuối cùng.
4. Lặp lại điều này với phần tiếp theo của các mục còn lại.
5. Khi danh sách nguồn bị trống, chúng tôi đã hoàn tất.

Để thực hiện điều này phải nhất thiết chúng ta phải tạo ra rất nhiều biến tạm thời, vòng lập chỉ mục, vv

Vì vậy, tôi tự hỏi nếu có một cách tiếp cận chức năng hơn? Ở góc nhìn đầu tiên, bộ sưu tập nguồn phải có khả năng hoạt động như một Stack trong việc cung cấp pop() PLUS cho khả năng xóa các mục theo chỉ mục trong khi lặp qua nó, nhưng sau đó sẽ không còn chức năng nữa.

Answer 1

Thử đuôi-đệ quy. (Chú thích là cần thiết để cảnh báo bạn nếu tối ưu đệ quy không xảy ra; trình biên dịch sẽ làm điều đó nếu nó có thể cho phép bạn chú thích hay không.)

Answer 2

Tôi yêu những loại câu đố:

case class Range(from:Int, to:Int) { 
    assert(from <= to) 

    /** Returns true if given Range is completely contained in this range */ 
    def contains(rhs: Range) = from <= rhs.from && rhs.to <= to 

    /** Returns true if given value is contained in this range */ 
    def contains(v: Int) = from <= v && v <= to 
} 

def collapse(rangelist: List[Range]) = 
    // sorting the list puts overlapping ranges adjacent to one another in the list 
    // foldLeft runs a function on successive elements. it's a great way to process 
    // a list when the results are not a 1:1 mapping. 
    rangelist.sortBy(_.from).foldLeft(List.empty[Range]) { (acc, r) => 
    acc match { 
     case head :: tail if head.contains(r) => 
     // r completely contained; drop it 
     head :: tail 
     case head :: tail if head.contains(r.from) => 
     // partial overlap; expand head to include both head and r 
     Range(head.from, r.to) :: tail 
     case _ => 
     // no overlap; prepend r to list 
     r :: acc 
    } 
    } 

Answer 3

Đây là giải pháp của tôi:

def merge(ranges:List[Range]) = ranges 
    .sortWith{(a, b) => a.from < b.from || (a.from == b.from && a.to < b.to)} 
    .foldLeft(List[Range]()){(buildList, range) => buildList match { 
    case Nil => List(range) 
    case head :: tail => if (head.to >= range.from) { 
     Range(head.from, head.to.max(range.to)) :: tail 
    } else { 
     range :: buildList 
    } 
    }} 
    .reverse 

merge(List(Range(1, 3), Range(4, 5), Range(10, 11), Range(1, 6), Range(2, 8))) 
//List[Range] = List(Range(1,8), Range(10,11))