Algorytm łączenia okresów :: 4programmers.net

0

Mam takie ciekawe zagadnienie:
Mam listę okresów zdefiniowanych jako:

List<Period> PeriodList;

class Period
{
  public DateTime DateStart { get; set; }
  public DateTime DateStop { get; set; }
}

Chciałbym tą listę zmienić tak aby okresy łączące się ze sobą oraz pokrywające się zamienić na jeden wpis, np: 2023-01-01 - 2023-01-10 oraz 2023-01-05 - 2023-01-20 zamienić na jedną pozycję: 2023-01-01 - 2023-01-20.

Czy jest na to jakiś algorytm pozwalający oprogramować taką operację?
Próbowałem to sam zrobić ale ilość możliwych przypadków mnie przerosła.
Może ktoś spotkał się z takim zagadnieniem?

Pozdrawiam

1

WojtexProgramista napisał(a):

Próbowałem to sam zrobić ale ilość możliwych przypadków mnie przerosła.

Czyli ile ? Czy nie zrobiłeś podejścia ?

Podam przykład. W naiwym podejściu do okresów wydaje się że istnienie części wspólnej wymaga 8 porównań, ale naprawdę 2 . Ale dojście do tego wymaga oswojenia z logiką matematyczną (co niektorzy tu czują się lepsi, że teorii nie znają - nie, to nie do ciebie @WojtexProgramista )

Gogole jest pełne range intersect, range ovelap, z dodatkiem C# lub bez

Jak wiesz, czy to zachodzi, to wiesz czy jest to wykonalne (i prosty wynik) , lub niewykonalne (dwa rozdzielne i kiszka)

0

A jakby posortować listę po DateStart ? To wtedy możne było by łatwiej?
Szkoda że nie umiem C#, musze się w końcu nauczyć. W pseudokodzie napisałbym tak


import scala.math._

case class Period(start: Int, stop: Int)

def joinPeriod(list: List[Period]): List[Period] = list match {
  case Nil => Nil
  case p :: Nil => List(p)
  case p1 :: p2 :: l if p1.stop >= p2.start => joinPeriod(Period(p1.start, max(p1.stop, p2.stop)) :: l)
  case p1 :: p2 :: l => p1 :: joinPeriod(p2 :: l)
}

val sortedList: List[Period] = List(Period(1, 2), Period(2, 3), Period(5, 10), Period(7, 8), Period(11, 12), Period(11, 13))

print(joinPeriod(periodList))

Dla uproszczenia zamieniłem typ datowy na zwykłego inta

0

Jakiś czas temu się tym zajmowałem, już nie pamiętam dobrze algorytmu i nie mam dostępu, ale wyglądało to mniej więcej tak: Na wejściu lista okresów, które mogą się pokrywać lub mogą się dotykać, na wyjściu lista rozłącznych okresów.

Sam algorytm był mniej więcej taki (okresy wejściowe posortowane wg daty początkowej):

Na początku jest pusta tablica okresów rozłącznych
Dla każdego okresu wejściowego:
1. Dla każdego okresu rozłącznego (na początku algorytmu nie ma ani jednego) sprawdzić, czy spełnia łącznie warunki:
  1. Data początkowa okresu wejściowego jest wcześniejsza od daty końcowej okresu rozłącznego.
  2. Data końcowa okresu wejściowego jest późniejsza od daty początkowej okresu rozłącznego.
2. Jeżeli znaleziono okres spełniający powyższe warunki, to należy go rozszerzyć tak, żeby obejmował skrajne daty dotychczasowego zakresu i zakresu okresu wejściowego.
3. W przeciwnym wypadku:
  1. Dodać nowy okres rozłączny o zakresie takim samym, jak okres wejściowy, tak, żeby okresy były w kolejności wg daty początkowej.
  2. Jeżeli to nie jest pierwszy okres i data początkowa wstawionego okresu jest o co najwyżej dzień późniejsza od daty końcowej poprzedniego okresu, zamienić te dwa okresy na jeden.
  3. Jeżeli to nie jest ostatni okres i data końcowa wstawionego okresu jest o co najwyżej dzień wcześniejsza od daty początkowej następnego okresu, zamienić te dwa okresy na jeden.
Tablica okresów rozłącznych zawiera okresy rozłączne będące wynikiem działania algorytmu

0

Szukać: interval merging algorithm:
https://duckduckgo.com/?t=ffab&q=interval+merging+algorithm&atb=v366-1&ia=web

Jakiś tam kod, (nie jestem biegły w C#, testowane lekko na https://repl.it, koniecznie dotestuj):

using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
    static void Main()
    {
        List<Period> periods = new List<Period>
        {
            new Period {DateStart = new DateTime(2023, 01, 01), DateStop = new DateTime(2023, 01, 10)},
            new Period {DateStart = new DateTime(2023, 01, 05), DateStop = new DateTime(2023, 01, 20)}
        };

        List<Period> mergedPeriods = MergePeriods(periods);

        foreach (Period period in mergedPeriods)
        {
            Console.WriteLine($"{period.DateStart} - {period.DateStop}");
        }
    }

    static List<Period> MergePeriods(List<Period> periods)
    {
        periods = periods.OrderBy(p => p.DateStart).ToList();
        List<Period> result = new List<Period>();

        foreach (Period period in periods)
        {
            if (!result.Any())
            {
                result.Add(period);
            }
            else
            {
                Period last = result.Last();
                if (last.DateStop < period.DateStart)
                {
                    result.Add(period);
                }
                else if (last.DateStop < period.DateStop)
                {
                    last.DateStop = period.DateStop;
                }
            }
        }
        return result;
    }
}

class Period
{
    public DateTime DateStart { get; set; }
    public DateTime DateStop { get; set; }
}