Вы можете:

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

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

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

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

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

Определите Список событий ;

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

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

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

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

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

Код находится здесь: 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.

Я бы

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: ("обработанные" диапазоны обозначены ** двойными звездочками ** )

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---|

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