找到重叠的时间间隔并将它们分割成新的时间间隔

Question

我需要一些帮助来在 C# 中构建一个算法，该算法采用时间间隔列表（开始、结束），找到任何重叠的时间段并在 start/end 处剪切它们。然后需要将它以“块”的形式合并在一起，这样最终的时间间隔就是一个周期。我会用图来说明。

到目前为止我的代码。它适用于两个时间间隔但引入三分之一或更多，它开始给出奇怪的结果:)

// Dummy objects
        var d1 = new TimeSlot(DateTime.Parse("2020-05-05 13:00 PM"), DateTime.Parse("2020-05-05 13:30 PM"), "1");
        var d3 = new TimeSlot(DateTime.Parse("2020-05-05 13:15 PM"), DateTime.Parse("2020-05-05 13:25 PM"), "2");
        var d2 = new TimeSlot(DateTime.Parse("2020-05-05 13:05 PM"), DateTime.Parse("2020-05-05 13:20 PM"), "3");

        List<TimeSlot> dates = new List<TimeSlot>();
        dates.Add(d1);
        dates.Add(d2);
        dates.Add(d3);

        List<TimeSlot> slicedDates = new List<TimeSlot>();

        IEnumerable<TimeSlot> dateContainer = dates;
        TimeSlot prev = dateContainer.First();
        dateContainer = dateContainer.Skip(1);

        foreach (TimeSlot date in dateContainer.OrderBy(x => x.StartDate))
        {
            var prevStartTime = prev.StartDate;
            var prevEndTime = prev.EndDate;

            if (date.StartDate < prev.EndDate)
            {
                TimeSlot leftSlice = new TimeSlot(prevStartTime, date.StartDate, prev.Name);
                slicedDates.Add(leftSlice);
            }

            if (date.EndDate < prevEndTime)
            {
                TimeSlot middleSlice = new TimeSlot(date.StartDate, date.EndDate, prev.Name + "," + date.Name);
                slicedDates.Add(middleSlice);

                TimeSlot rightSlice = new TimeSlot(date.EndDate, prevEndTime, prev.Name);
                slicedDates.Add(rightSlice);
            }

            prev = date;
        }

并且输出三个错误的时间间隔：

05-05-2020 13:00:00 => 05-05-2020 13:05:00: 1
05-05-2020 13:05:00 => 05-05-2020 13:20:00: 1,3
05-05-2020 13:05:00 => 05-05-2020 13:15:00: 3
05-05-2020 13:20:00 => 05-05-2020 13:30:00: 1

Answer 1

我稍微调整了一下算法：

        var d1 = new TimeSlot(DateTime.Parse("2020-05-05 13:00 PM"), DateTime.Parse("2020-05-05 13:30 PM"), "1");
        var d3 = new TimeSlot(DateTime.Parse("2020-05-05 13:15 PM"), DateTime.Parse("2020-05-05 13:25 PM"), "2");
        var d2 = new TimeSlot(DateTime.Parse("2020-05-05 13:05 PM"), DateTime.Parse("2020-05-05 13:20 PM"), "3");

        List<TimeSlot> dates = new List<TimeSlot>();
        dates.Add(d1);
        dates.Add(d2);
        dates.Add(d3);

        List<TimeSlot> slicedDates = new List<TimeSlot>();

        IEnumerable<TimeSlot> dateContainer = dates;

        // Created an ordered list of Start & End dates.
        var times = dateContainer.Select(x => x.StartDate);
        times = times.Concat(dateContainer.Select(x => x.EndDate));
        var orderedTimes = times.Distinct().OrderBy(x => x);
        var prev = orderedTimes.First();
        times = orderedTimes.Skip(1);

        foreach (var time in times)
        {
            var names = new List<string>();
            foreach (TimeSlot date in dateContainer)
            {
                // Add the TimeSlot if it's in range
                if (prev >= date.StartDate && time <= date.EndDate)
                {
                    names.Add(date.Name);
                }
            }

            var name = string.Join(",",names);
            TimeSlot slot = new TimeSlot(prev, time, name);
            slicedDates.Add(slot);

            prev = time;
        }

Answer 2

还有一个可以玩：

List<TimeSlot> originalSlots = new List<TimeSlot>() {
    new TimeSlot(DateTime.Parse("2020-05-05 13:00 PM"), DateTime.Parse("2020-05-05 13:30 PM"), "1"),
    new TimeSlot(DateTime.Parse("2020-05-05 13:15 PM"), DateTime.Parse("2020-05-05 13:25 PM"), "2"),
    new TimeSlot(DateTime.Parse("2020-05-05 13:05 PM"), DateTime.Parse("2020-05-05 13:20 PM"), "3")
};

var times = originalSlots.Select(ts => ts.StartDate)
    .Concat(originalSlots.Select(ts => ts.EndDate))
    .Distinct().OrderBy(dt => dt);
var slicedSlots = Enumerable.Range(0, times.Count() - 1)
    .Select(i => new TimeSlot(times.ElementAt(i), times.ElementAt(i + 1), ""));

foreach(TimeSlot ts in slicedSlots )
{                
    ts.Name = String.Join(",", 
        originalSlots
        .Where(origTS => ts.StartDate >= origTS.StartDate && ts.EndDate <= origTS.EndDate)
        .Select(origTS => origTS.Name)
    );
    Console.WriteLine(ts);
}

手动完成的分析：

Original slots: 

     |------- 1 -------|
              |- 2 -| 
        |--- 3 --|
     |  |  |  |  |  |  |
    00 05 10 15 20 25 30

Sliced slots:

     |-a|--b--|-c|-d|-e|
     |  |  |  |  |  |  |
    00 05 10 15 20 25 30

Each slot contains:

    a: 1
    b: 1,3
    c: 1,2,3
    d: 1,2
    e: 1

CODE 的输出：

5/5/2020 13:00:00 => 5/5/2020 13:05:00 : 1
5/5/2020 13:05:00 => 5/5/2020 13:15:00 : 1,3
5/5/2020 13:15:00 => 5/5/2020 13:20:00 : 1,2,3
5/5/2020 13:20:00 => 5/5/2020 13:25:00 : 1,2
5/5/2020 13:25:00 => 5/5/2020 13:30:00 : 1

我的时间段class:

public class TimeSlot
{

    public DateTime StartDate;
    public DateTime EndDate;
    public String Name;

    public TimeSlot(DateTime start, DateTime end, String name)
    {
        StartDate = start;
        EndDate = end;
        Name = name;
    }

    public override string ToString()
    {
        return $"{StartDate} => {EndDate} : {Name}";
    }

}

找到重叠的时间间隔并将它们分割成新的时间间隔

Find overlapping time intervals and slice them into new ones

c#

time

intervals