Задача алгоритма: диапазон дат слияния

Question

Я столкнулся с интересной проблемой:

• У меня есть несколько диапазонов дат, которые могут перекрываться
• у каждого из них есть имя

Можно ли "перекрывать" эти диапазоны? То есть сгенерировать:

• новый набор диапазонов, где ни один не перекрывает другие
• каждый из этого нового диапазона имеет список соответствующих имен

Может быть, я смогу сделать это немного более наглядным. Это то, что у меня первое:

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

Вот что я хотел бы получить:

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

Я нашел решение, которое работает, но не элегантно:

1. Я преобразую каждый диапазон (от, до) в список дней (d1, d2, d3 и т. Д.)
2. Я группирую имена по дням
3. Я объединяю группы с одинаковыми именами для воссоздания диапазонов

Можете ли вы придумать лучшее решение? Я работаю с C #, но любая независимая от языка идея будет высоко ценится. Спасибо!

Answer 1

Я бы

1. Хранить неупорядоченный список «открытых» диапазонов
2. Начните с первого дня и добавьте первый диапазон в список открытых диапазонов.
3. Перемещение до следующей границы диапазона (будь то начало или закрытие). Создайте свой первый «выходной» диапазон: начиная с первого дня и заканчивая тем же днем. В нем есть предметы в вашем списке открытых диапазонов.
4. Если обнаруженный диапазон уже находится в списке открытых диапазонов, удалите его. В противном случае добавьте его.
5. Повторите 3 и 4, двигаясь вдоль линии.

Я определенно плохо объяснил это. Я скоро напишу код для этого. Но до тех пор вот что произойдет в вашем решении:

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

---

Альтернативный метод

Вы можете сделать это:

1. Хранить упорядоченный список «диапазонов вывода». Это позволяет легко проверить, находится ли точка в пределах диапазона, а также какие диапазоны следуют друг за другом.
2. Возьмите диапазон из ваших входных диапазонов.
3. Проверьте, полностью ли он до или после всех выходных диапазонов, и обработайте его соответствующим образом. Пропустите следующие шаги и вернитесь к шагу 2, если это так.
4. Сравните начальную точку с диапазонами вывода
5. Если он находится перед любым другим выходным диапазоном, добавьте новый выходной диапазон от его начала до начала первого выходного диапазона.
6. Если это между уже существующим выходным диапазоном, разделите этот выходной диапазон в этой точке. Первая часть будет содержать тех же «родителей», а вторая часть будет иметь тех же родителей + новый диапазон ввода.
7. Теперь сравните его конечную точку с выходными диапазонами.
8. Если это после любого другого выходного диапазона, добавить новый выходной диапазон от конца последнего выходного диапазона до его конца.
9. Если это между уже существующим выходным диапазоном, разделите этот выходной диапазон в этой точке. Вторая часть будет содержать тех же «родителей», а первая часть будет иметь тех же родителей + новый диапазон ввода
10. Добавьте текущий входной диапазон как часть ко всем диапазонам между двумя «обработанными» диапазонами на шагах 6 и 9, если таковые имеются.
11. Повторите 2-6 для всех входных диапазонов.

Вот первые несколько шагов с использованием данных примера + другой диапазон D: («обработанные» диапазоны, обозначенные **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

У меня есть код, который делает это.Он основан на том, что набор входных данных упорядочен по from, а затем to (т. Е. Если бы это был SQL, это было бы ORDER BY from_value, to_value), но после этого он вполне оптимален.

Моя реализацияв основном делает то, что @ Джастин Л. ' ответ описывает, поэтому, если вы просто хотите текстовое описание, посмотрите на его ответ для алгоритма.

Кодздесь: LVK.DataStructures , и файлы, которые вы хотите просмотреть:

• Range.cs
• RangeExtensions.cs , в частности метод Slice на строке 206 и далее.

Чтобы использовать его:

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

Это даст вам одинновый диапазон для каждого среза, и для каждого такого диапазона у вас будет свойство .Data, содержащее ссылки на вспомогательные диапазоны.

т.е.для вашего исходного примера вы получите именно то, что вы хотите, отдельные диапазоны с соответствующими диапазонами a, b, c и т. д. в свойстве .Data.

Классы могут использовать другие части моей библиотеки классов,что все там.Если вы решите использовать его, просто скопируйте части, которые вы хотите использовать.

Если вас интересует только реализация, ее можно найти в файле RangeExtensions.cs , строка 447 и далее, метод InternalSlice.

Answer 3

Возможно, вы захотите взглянуть на Деревья интервалов .

Answer 4

Вы можете:

1. отсортировать список всех дат (объединяя даты от и до)
2. , затем, следуя этому списку, каждый новый диапазон будет от одной даты доследующая начальная или конечная дата, отличная от предыдущей.

Для именования новых диапазонов имеет смысл иметь список исходных имен диапазонов, который содержит текущий новый диапазон, и каждый развы нажимаете дату окончания, удаляете старое имя диапазона из списка, и каждый раз, когда вы нажимаете дату начала, добавляете его имя в список.

Answer 5

1. Сначала у меня есть список, я не знаю его длины, но у меня есть 3 символа
2. проверить на один слот, если А есть? добавить «А», если Б там? добавить 'B', если c там? добавить 'C'
3. перейти в другой слот, цикл как # 2
4. заканчивается, когда в новый новый слот ничего не добавляется
5. Я получил список
6. Свести список

Answer 6

Сделайте следующее:

Создайте класс 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;
    }
}

Определите List<DateEvent> events;

Добавьте дату начала и окончания каждого диапазона в список:

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));
}

Сортировка событий.

events.Sort();

Теперь установите выходной класс:

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

Наконец, пройдитесь по событиям, поддерживая, какие диапазоны присутствуют:

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);
}

Это должно сработать.Обратите внимание, что я не сделал конструкторы, и код немного уродлив, но, надеюсь, это передает общую идею.