thuật toán thách thức: ngày sáp nhập phạm vi

Question

Tôi đang phải đối mặt với một vấn đề thú vị:

• Tôi có một vài phạm vi ngày có thể chồng lên nhau
mỗi trong số họ
• có một cái tên

Có thể các cụm từ "bỏ qua" trùng lặp? Đó là, để tạo ra:

• một bộ mới của dãy nơi không có sự chồng chéo với những người khác
• mỗi dòng sản phẩm mới này có một danh sách các tên tương ứng

lẽ tôi có thể làm điều này nhiều hơn một chút đồ họa. Đây là những gì tôi có đầu tiên:

a |------------------------------| 
b     |-------------------| 
c   |-----------------| 

Đây là những gì tôi muốn để có được:

|------|---------|-------|-----|-----| 
     a  a,c  a,b,c a,b b 

Tôi tìm thấy một giải pháp mà các loại công trình, nhưng mà không phải là thanh lịch:

1. Tôi chuyển đổi từng phạm vi (từ, sang) thành danh sách ngày (d1, d2, d3, v.v.)
2. Tôi tên nhóm theo ngày
3. Tôi tổng hợp các nhóm có cùng tên để tạo lại phạm vi

Bạn có thể nghĩ ra giải pháp tốt hơn không? Tôi đang làm việc với C# nhưng bất kỳ ý tưởng độc lập ngôn ngữ nào cũng sẽ được đánh giá cao. Cảm ơn!

Answer 1

tôi sẽ

1. Giữ một danh sách có thứ tự của "mở" khoảng
2. Bắt đầu từ ngày 1, và thêm phạm vi đầu tiên vào danh sách dải mở.
3. Di chuyển đến ranh giới phạm vi tiếp theo (bắt đầu hoặc đóng). Tạo phạm vi "đầu ra" đầu tiên của bạn: bắt đầu từ ngày 1, kết thúc vào ngày đó. Trong đó là các mục trong danh sách phạm vi mở của bạn.
4. Nếu phạm vi gặp phải đã có trong danh sách phạm vi mở, hãy xóa nó. Nếu không, hãy thêm nó.
5. Lặp lại 3 và 4, di chuyển dọc theo dòng.

Tôi chắc chắn đã làm một công việc tồi để giải thích. Tôi sẽ viết một số mã cho việc này sớm thôi. Nhưng cho đến lúc đó, đây là những gì sẽ xảy ra trong giải pháp của bạn:

a |------------------------------| 
b     |-------------------| 
c   |-----------------| 

 
1. Start at day 1, add A to open ranges list, which now contains [A] 
2. Move to the start of C. First RESULT RANGE: A range from Day 1 to C's start, 
     with a value A. (what is in your open ranges list) 
3. Add C to the open ranges list, which now contains [A,C] 
4. Move to the start of B. Second RESULT RANGE: A range from C's start to B's 
     start, with a value A,C. (what is in your open ranges list) 
5. Add B to the open ranges list, which now contains [A,C,B] 
6. Move to the end of C. Third RESULT RANGE: A range from B's start to C's end, 
     with a value of A,C,B. 
7. Remove C from the open ranges list, which now contains [A,B] 
8. Move to the end of A. Fourth RESULT RANGE: A range from C's end to A's end, 
     with a value of A,B 
9. Remove A from the open ranges list, which now contains [B] 
10. Move to the end of A. Fourth RESULT RANGE: A range from A's end to B's end, 
     with a value of B 

RESULT RANGES 
1. from Day 1 to C's start: A 
2. from C's start to B's start: A,C 
3. from B's start to C's end: A,C,B 
4. from C's end to A's end: A,B 
5. from A's end to B's end: B 

---

Phương pháp thay thế

Bạn có thể làm điều này:

1. Giữ một danh sách có thứ tự các "dải đầu ra ". Điều này giúp bạn dễ dàng kiểm tra xem một điểm có nằm trong phạm vi không, và phạm vi nào cũng theo sau eachother.
2. Lấy một dải từ phạm vi nhập liệu của bạn.
3. Kiểm tra xem nó có hoàn toàn trước hoặc hoàn toàn sau tất cả các dải đầu ra và xử lý tương ứng. Bỏ qua các bước tiếp theo và quay lại bước 2, nếu có.
4. So sánh điểm bắt đầu với phạm vi đầu ra
5. Nếu trước phạm vi đầu ra khác, hãy thêm phạm vi đầu ra mới từ đầu đến đầu phạm vi đầu ra đầu tiên.
6. Nếu điều này nằm giữa phạm vi đầu ra đã tồn tại, hãy chia phạm vi đầu ra đó tại thời điểm đó. Phần đầu tiên sẽ giữ cùng một "cha mẹ", và phần thứ hai sẽ có cùng cha mẹ + phạm vi đầu vào mới.
7. Bây giờ, hãy so sánh điểm kết thúc với phạm vi đầu ra.
8. Nếu nó nằm sau bất kỳ phạm vi đầu ra nào khác, hãy thêm một phạm vi đầu ra mới từ cuối dải đầu ra cuối cùng đến kết thúc.
9. Nếu điều này nằm giữa phạm vi đầu ra đã tồn tại, hãy chia phạm vi đầu ra đó tại thời điểm đó. Phần thứ hai sẽ giữ cùng "cha mẹ" và phần đầu sẽ có cùng cha mẹ + phạm vi nhập mới
10. Thêm phạm vi nhập hiện tại làm một phần cho tất cả phạm vi ở giữa hai dải "đã xử lý" trong bước 6 và 9, nếu có.
11. Lặp lại 2-6 cho tất cả các phạm vi nhập.

Đây là một vài bước đầu tiên, bằng cách sử dụng dữ liệu mẫu + một dãy D: (dãy "xử lý" được chỉ định bởi **double stars**)

a |------------------------------| 
b     |-------------------| 
c   |-----------------| 
d  |------------------------| 

 

1. 
    Process A 
    Output ranges: |--------------A---------------| 
2. 
    Process B 
    - Start of B is in **A**; split A in two: 
        |-------A-------|------AB------| 
    - End of B is after any output range range; 
     creating new output range at end 
        |-------A-------|------AB------|---B---| 
    - Nothing was/is in between **A** and (nothing) 
3. 
    Process C 
    - Start of C is in **A**; split A in two: 
        |---A----|--AC--|------AB------|---B---| 
    - End of C is in **AB**; split AB in two: 
        |---A----|--AC--|--ABC--|--AB--|---B---| 
    - There were/are no ranges between **A** and **AB** 

4. 
    Process D 
    - Start of D is in **A**; split A in two: 
        |-A-|-AD-|--AC--|--ABC--|--AB--|---B---| 
    - End of D is in **AB**; split AB in two: 
        |-A-|-AD-|--AC--|--ABC--|ABD|AB|---B---| 
    - Ranges AC and ABC were/are in between **A** and **AB** 
        |-A-|-AD-|--ACD-|-ABCD--|ABD|AB|---B---| 

Final output:  |-A-|-AD-|--ACD-|-ABCD--|ABD|AB|---B---| 

Answer 2

Bạn có thể muốn có cái nhìn tại Interval Trees .

Answer 3

Bạn có thể:

1. sắp xếp danh sách của tất cả các ngày (kết hợp các từ và đến ngày tháng)
2. sau đó chạy dọc theo danh sách này, mỗi dòng sản phẩm mới sẽ là từ một ngày khi bắt đầu tiếp theo hoặc cuối ngày khác với ngày trước.

Để đặt tên dải ô mới, sẽ có ý nghĩa khi có danh sách tên dải ô gốc hiện tại chứa và mỗi lần bạn nhấn vào ngày kết thúc, hãy xóa tên dải cũ khỏi danh sách và mỗi tiem bạn nhấn một ngày bắt đầu, thêm tên của nó vào danh sách.

Answer 4

Làm điều này:

Tạo một lớp học Event.

class DateEvent : IComparable<DateEvent> 
{ 
    public Date Date; 
    public int DateRangeId; 
    public bool IsBegin; // is this the start of a range? 

    public int CompareTo(DateEvent other) 
    { 
     if (Date < other.Date) return -1; 
     if (Date > other.Date) return +1; 
     if (IsBegin && !other.IsBegin) return -1; 
     if (!IsBegin && other.IsBegin) return +1; 
     return 0; 
    } 
} 

Xác định một List<DateEvent> events;

Thêm bắt đầu và ngày kết thúc của mỗi loạt vào danh sách:

for (int i = 0; i < dateRanges.Length; ++i) 
{ 
    DateRange r = dateRanges[i]; 
    events.Add(new DateEvent(r.BeginDate, i, true)); 
    events.Add(new DateEvent(r.EndDate, i, false)); 
} 

Sắp xếp các sự kiện.

events.Sort(); 

Giờ thiết lập một lớp học đầu ra:

class OutputDateRange 
{ 
    public Date BeginDate; 
    public Date EndDate; 
    public List<string> Names; 
} 

Cuối cùng, đi qua những biến cố, duy trì trong đó khoảng có mặt:

List<int> activeRanges; 
List<OutputDateRange> output; 
Date current = events[0].Date; 
int i = 0; 

while (i < events.Length;) 
{ 
    OutputDateRange out = new OutputDateRange(); 
    out.BeginDate = current; 

    // Find ending date for this sub-range. 
    while (i < events.Length && events[i].Date == current) 
    { 
     out.EndDate = events[i].Date; 
     if (events[i].IsBegin) 
      activeRanges.Add(events[i].DateRangeId); 
     else 
      activeRanges.Remove(events[i].DateRangeId); 
     ++i; 
    } 

    if (i < events.Length) 
     current = events[i].Date; 

    foreach (int j in activeRanges) 
     out.Names.Add(dateRanges[j].Name); 

    output.Add(out); 
} 

Điều đó sẽ làm các trick. Lưu ý rằng tôi đã không thực hiện các nhà xây dựng, và mã là một chút xấu xí, nhưng hy vọng rằng truyền tải ý tưởng chung.

Answer 5

Tôi có mã thực hiện việc này. Nó dựa trên bộ đầu vào được đặt hàng bởi from và sau đó to (ví dụ: nếu nó là SQL, nó sẽ là ORDER BY from_value, to_value), nhưng sau đó nó là khá tối ưu.

Việc triển khai của tôi về cơ bản thực hiện mô hình của @Justin L., vì vậy nếu bạn chỉ muốn mô tả văn bản, hãy xem câu trả lời của mình cho thuật toán.

Mã này là ở đây: LVK.DataStructures, và các tập tin bạn muốn xem xét là:

• Range.cs
• RangeExtensions.cs, đặc biệt là phương pháp Slice tại line 206 trở đi.

Để sử dụng nó:

List<Range<DateTime>> ranges = ... 
var slices = ranges.Slice(); 

này sẽ cung cấp cho bạn một dòng sản phẩm mới cho mỗi lát, và đối với từng phạm vi như vậy bạn sẽ có một tài sản có chứa tài liệu tham khảo về các dãy góp .DATA.

tức là. cho ví dụ ban đầu của bạn, bạn sẽ nhận được chính xác những gì bạn muốn, phạm vi riêng lẻ, với các phạm vi đóng góp a, b, c, vv trong thuộc tính .Data.

Các lớp học có thể sử dụng các phần khác của thư viện lớp học của tôi, tất cả đều ở đó. Nếu bạn quyết định sử dụng nó, chỉ cần sao chép ra các phần bạn muốn sử dụng.

Nếu bạn chỉ quan tâm đến việc triển khai, nó có thể được tìm thấy trong tệp RangeExtensions.cs, line 447 và trở đi, phương pháp InternalSlice.

Answer 6

1. Tôi có một danh sách đầu tiên, tôi không biết chiều dài của nó, nhưng tôi đã nhận 3 chars
2. séc cho một khe, nếu A có? thêm 'A', nếu B ở đó? thêm 'B', nếu c có? thêm 'C'
3. đi đến khe khác, chu kỳ như # 2
4. kết thúc khi không có gì thêm vào một khe mới
5. tôi có danh sách
6. flatten danh sách