Thuật toán: Merge phân đoạn chồng chéo

Question

Tôi đã sau ADT (không sắp xếp): List<Segment>

//direction is from 0 to 2pi 
class Segment { 
    int start; 
    int end; 
} 

Họ đại diện cho ví dụ tình trạng này:

Làm thế nào để làm cho giai đoạn sáp nhập (mũi tên màu xanh lá cây trong ví dụ)? Rõ ràng tôi cần phải lặp qua danh sách và mỗi phân đoạn so sánh với tất cả các phân đoạn khác và cho mỗi cặp vợ chồng nếu có thể thực hiện hợp nhất đơn giản (điều này thật dễ dàng). Nhưng sau đó trong lần lặp thứ hai, tôi cần bằng cách nào đó để trở về đầu danh sách và bắt đầu lại vv ... Vì vậy, tôi đấu tranh để tìm cách thuật toán này sẽ hội tụ như thế nào.

CHỈNH SỬA: Các đoạn có thể là hình tròn - Từ 1.75pi đến 0.5pi, v.v ...

Answer 1

Sắp xếp các phân đoạn theo thời gian bắt đầu.

Tạo ngăn xếp sẽ lưu trữ khoảng thời gian đã hợp nhất.

Thêm phần tử đầu tiên của mảng được sắp xếp vào stack, sau đó cho mỗi phần tử trong mảng, so sánh nó với phần tử ở đầu stack

Nếu thời gian bắt đầu lớn hơn thời gian kết thúc của phần tử ở đầu ngăn xếp, thêm khoảng thời gian vào ngăn xếp.

Nếu thời gian bắt đầu nhỏ hơn thời gian kết thúc của phần tử ở đầu ngăn xếp, hãy cập nhật thời gian kết thúc của phần tử ở đầu ngăn xếp để khớp với thời gian kết thúc của phần tử mới.

Khi toàn bộ mảng được xử lý, ngăn xếp kết quả sẽ chứa khoảng thời gian đã hợp nhất.

thực hiện trên java:

/** 
* Definition for an interval. 
* public class Interval { 
*  int start; 
*  int end; 
*  Interval() { start = 0; end = 0; } 
*  Interval(int s, int e) { start = s; end = e; } 
* } 
*/ 
public class Solution { 
    public List<Interval> merge(List<Interval> intervals) { 
     Deque<Interval> stack = new ArrayDeque<Interval>(); 

     Collections.sort(intervals, new Comparator<Interval>() { 
       public int compare(Interval p1, Interval p2) { 
        return Integer.compare(p1.start, p2.start); 
       } 
      } 
     ); 

     if (intervals.size() < 1) { 
      return intervals; 
     } 
     stack.push(intervals.get(0)); 

     for (int j = 1; j < intervals.size(); j++) { 
      Interval i = intervals.get(j); 
      Interval top = stack.peek(); 
      if (top.end < i. start) { 
       stack.push(i); 
      } 
      else if (top.end < i.end) { 
       top.end = i.end; 
      } 
     } 
     return new ArrayList<Interval>(stack); 

    } 
} 

Answer 2

Sắp xếp các phân đoạn của bạn theo điểm bắt đầu. Sau đó, đối với mỗi phân đoạn, nếu điểm bắt đầu của nó nằm giữa điểm bắt đầu và điểm kết thúc của đoạn trước và điểm cuối của nó lớn hơn điểm kết thúc của đoạn trước, hãy đặt điểm đến của đoạn trước đó thành điểm cuối của đoạn này và xóa/bỏ qua phân đoạn hiện tại.

Nếu phân đoạn hiện tại hoàn toàn được bao gồm trong phân đoạn trước, thì chỉ cần xóa/bỏ qua phân khúc đó.

Đây là O(n log n) do sắp xếp và bạn không cần phải so sánh từng phân đoạn với tất cả các phân đoạn khác.

Hãy cẩn thận cách bạn xóa hoặc bỏ qua. Nó phải là một hoạt động O(1). Ví dụ: giữ một biến luôn lưu trữ phân đoạn không bị xóa trước đó và có thể một số cờ cho các phân đoạn đã loại bỏ để bạn biết những biến nào cần thu thập ở cuối. Hoạt động .remove() trên bộ sưu tập có thể là O(n) và bạn muốn tránh điều đó.

Answer 3

Đặt tất cả các thiết bị đầu cuối trong một mảng duy nhất và gán cho họ một cực (+ sau đó -). Sau đó sắp xếp danh sách.

Khi bạn đi ngang qua danh sách bằng cách tăng giá trị, nó đủ để cập nhật bộ đếm phân đoạn chồng chéo.

0+ 0.75- 0.5+ 1- 1.25+ 2- 

sau đó, được sắp xếp,

0+ 0.5+ 0.75- 1- 1.25+ 2- 

cung cấp cho các tội (khởi tạo tại 0)

1 2 1 0 1 0 

do đó các giới hạn khoảng cách (về chuyển 0 to >0 hoặc >0 to 0)

0 1 1.25 2 

---

Điều này cũng có thể được thực hiện hoàn toàn tại chỗ, mà không cần thêm cờ.

Bạn sắp xếp các giá trị start và end riêng biệt, tại chỗ (không di chuyển Segments nói chung); theo cách này các cực vẫn còn tiềm ẩn.

Sau đó duyệt qua danh sách dưới dạng hợp nhất hai danh sách được sắp xếp (sử dụng hai chỉ mục độc lập) và duy trì bộ đếm chồng chéo. Bạn có thể ghi đè các giới hạn tại chỗ vì kết quả của quá trình hợp nhất không có nhiều khoảng thời gian hơn.

Bắt đầu từ

[0 0.75][0.5 1][1.25 2] 

cả hai danh sách được vô tình đã được sắp xếp.

0 0.5 1.25 (+) 
0.75 1 2 (-) 

Tiến hành việc hợp nhất, mà sẽ lựa chọn các yếu tố theo thứ tự

+ + - - + - 

và kết quả cuối cùng thu được bằng cách thay đổi giá trị

[0 1][1.25 2][x x] 

---

Trong trường hợp quan hệ trên các giới hạn, tốt hơn là xử lý + và - theo thứ tự sao cho y tránh phát ra hai giới hạn bằng nhau.

Answer 4

Tôi sẽ thêm vào các câu trả lời khác cách tiếp cận cho vòng tròn, nghĩa là bạn nên làm gì nếu bạn có một số đoạn lặp trên 2pi.

Có hai cách để xử lý việc này. Một là đơn giản chia từng phân đoạn như vậy thành hai: một đi từ bất cứ đâu đến 2pi, cái kia đi từ số không đến bất cứ đâu. Sau này, giải quyết vấn đề như thể nó không phải là vòng tròn, và sau đó nếu bạn có một phân đoạn bắt đầu từ số không, và một đoạn kết thúc tại 2pi, sau đó chỉ cần hợp nhất chúng.

Cách tiếp cận thứ hai dành riêng cho câu trả lời của Yves Daoust. Có tất cả những gì bạn cần là để biết có bao nhiêu phân đoạn bao phủ điểm 0 (bạn có thể dễ dàng tính toán điều này); sau này, bạn khởi tạo "đếm" không bằng 0, nhưng với số lượng các phân đoạn che phủ này.