Find overlapping time intervals and slice them into new ones

user_3185856 0
Viewed 562

I need some help to construct an algorithm in C# that takes a list of time intervals (start, end), find any overlapping time periods and cut them at their start/end. Then it needs to be merged together in "blocks" so that the final time interval is just one period. I'll illustrate it with a drawing.

enter image description here

My code so far. It works great for two time intervals but introducing a third or more, it starts to give strange results :)

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

And output for the three time intervals which is wrong:

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
intervals time c#
2 Answers

I adjusted the algorithm a bit:

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

Here's another one to play with:

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

Analysis done by HAND:

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

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

My TimeSlot 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}";
    }

}
user_23300530
Related