Ответ 1

Я бы

• Сохранять неупорядоченный список "открытых" диапазонов
• Начните с первого дня и добавьте первый диапазон в список открытых диапазонов.
• Переместить до следующей границы диапазона (начинать или закрывать). Создайте свой первый "выходной" диапазон: начиная с 1-го дня, заканчивая в этот день. В нем находятся элементы в списке открытых диапазонов.
• Если найденный диапазон уже находится в списке открытых диапазонов, удалите его. В противном случае добавьте его.
• Повторите 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 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 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 start to C 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 end to A 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 end to B end,
      with a value of B

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

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

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

• Сохраняйте упорядоченный список "диапазонов вывода". Это позволяет легко проверить, находится ли точка в пределах диапазона, а также какие диапазоны следуют друг за другом.
• Возьмите диапазон из диапазонов ввода.
• Проверьте, полностью ли он полностью или полностью после всех диапазонов вывода, и обрабатывайте соответственно. Пропустите следующие шаги и вернитесь к шагу 2, если это так.
• Сравните начальную точку с выходными диапазонами
• Если это до любого другого выходного диапазона, добавьте новый выходной диапазон от его начала до начала первого выходного диапазона.
• Если это находится между уже существующим выходным диапазоном, разделите этот диапазон вывода на эту точку. Первая часть будет содержать те же "родители", а вторая часть будет иметь те же родители + новый диапазон ввода.
• Теперь сравните его конечную точку с выходными диапазонами.
• Если после любого другого выходного диапазона добавьте новый выходной диапазон от конца последнего выходного диапазона до конца.
• Если это находится между уже существующим выходным диапазоном, разделите этот диапазон вывода на эту точку. Вторая часть будет содержать те же "родители", и первая часть будет иметь те же родители + новый диапазон ввода
• Добавьте текущий диапазон ввода как часть ко всем диапазонам между двумя "обработанными" диапазонами на шагах 6 и 9, если они есть.
• Повторите 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---|

Ответ 2

Возможно, вы захотите посмотреть Интервальные деревья.

Ответ 3

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

Моя реализация в основном делает то, что описывает @Justin L. ответ, поэтому, если вы просто хотите текстовую описание, посмотрите на его ответ на алгоритм.

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

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

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

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

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

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

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

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

Ответ 4

Вы можете:

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

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

Ответ 5

Сделайте это:

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

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

Ответ 6

• Сначала у меня есть список, я не знаю его длины, но у меня есть 3 символа
• проверить на один слот, если A там? добавьте 'A', если B там? добавить 'B', если c там? добавить 'C'
• перейдите в другой слот, как # 2
• конец, когда ничего не добавлено в новый слот
• Я получил список
• сгладить список