C# Find All Missing Segments In Time

Question

I need to find the missing segments within a 10 minute period and I am wondering the best route to take.

Lets say I have three segments in time.

1. 2:30 - 3:43 minute segment.
2. 4:25 - 4:59 minute segment.
3. 7:21 - 9:55 minute segment.

With C#, I have a full 10:20 minute segment in time. I need to find the missing segments when I already have 3 segments from above.

So the segments I need to calculate with C# are the following

1. 0:00 - 2:29 minute segment.
2. 3:44 - 4:24 minute segment.
3. 5:00 - 7:20 minute segment.
4. 9:56 - 10:20 minute segment.

So do I calculate those 4 segments from the 3 segments I already know above?

I think my best route is to just do a for loop and count all the way up to 10:20 in seconds and check if that current second exists within the 3 segments. If not, add that second to the missing segment.

Answer 1

I do not think it is a good idea to check for each second if it belongs to an interval. I think this problem could be solved having an O(n) complexity, of course using some .NET classes to structure the input that will make everything more easy. Full fiddle here.

private static List<Tuple<TimeSpan,TimeSpan>> ComputeMissingTimeSpans(List<Tuple<TimeSpan,TimeSpan>> availableIntervals, TimeSpan minSpan, TimeSpan maxSpan)
    {
        List<Tuple<TimeSpan,TimeSpan>> missingTime = new List<Tuple<TimeSpan,TimeSpan>>();
        if(availableIntervals.Count == 0)
        {
            missingTime.Add(new Tuple<TimeSpan, TimeSpan>(minSpan, maxSpan));
            return missingTime;
        }

        foreach(var interval in availableIntervals){
            if((interval.Item1 - minSpan).TotalSeconds > 1 ) 
            {
                missingTime.Add(new Tuple<TimeSpan, TimeSpan>(minSpan, interval.Item1.Add(TimeSpan.FromSeconds(-1))));
            }

            minSpan = interval.Item2.Add(TimeSpan.FromSeconds(1));
        }

        if((maxSpan - minSpan).TotalSeconds > 1)
            missingTime.Add(new Tuple<TimeSpan, TimeSpan>(minSpan, maxSpan));

        return missingTime;
    }

You can easy adapt this function to your needs.

Answer 2

Following the bright idea of @Matt Johnson, and for a more generic solution also suitable for long and/or periods, you could create a TimeSlot struct:

public struct TimeSlot
{
    private DateTime _start;
    private TimeSpan _span;

    public DateTime Start
    {
        get
        {
            if (_start == null)
            {
                _start = DateTime.Today;
            }
            return _start;
        }

        set
        {
            _start = value;
        }
    }

    public TimeSpan Span
    {
        get
        {
            if (_span == null)
            {
                _span = new TimeSpan(0);
            }
            return _span;
        }

        set
        {
            if (value.Ticks >= 0)
            {
                _span = value;
            }
        }
    }

    public DateTime End
    {
        get
        {
            return Start.Add(Span);
        }
    }

    public TimeSlot(DateTime start, TimeSpan span)
    {
        _start = start;
        _span = span.Ticks >= 0 ? span : new TimeSpan(0);
    }
}

Then you can run code like this where you first find the leading segment, then those segments in between, and finally the trailing segment:

public static void SlotDemo()
{
    DateTime startTime = DateTime.Today;
    DateTime endTime = startTime.Add(new TimeSpan(0, 10, 20));

    List<TimeSlot> segments = new List<TimeSlot>();
    segments.Add(new TimeSlot(startTime.Add(new TimeSpan(0, 2, 30)), new TimeSpan(0, 1, 13)));
    segments.Add(new TimeSlot(startTime.Add(new TimeSpan(0, 4, 25)), new TimeSpan(0, 0, 35)));
    segments.Add(new TimeSlot(startTime.Add(new TimeSpan(0, 7, 21)), new TimeSpan(0, 2, 34)));

    for (int i = 0; i < segments.Count; i++)
    {
        Console.WriteLine("s: {0:mm':'ss}  d: {1:mm':'ss}  e: {2:mm':'ss}", segments[i].Start, segments[i].Span, segments[i].End);
    }
    Console.WriteLine();

    if (!segments[0].Start.Equals(startTime))
    {
        TimeSlot firstSlot = new TimeSlot(startTime, segments[0].Start.Subtract(startTime));
        segments.Insert(0, firstSlot);
    }

    for (int i = 0; i < segments.Count; i++)
    {
        Console.WriteLine("s: {0:mm':'ss}  d: {1:mm':'ss}  e: {2:mm':'ss}", segments[i].Start, segments[i].Span, segments[i].End);
    }
    Console.WriteLine();

    for (int i = 0; i < segments.Count - 1; i++)
    {
        if (segments[i].End != segments[i + 1].Start)
        {
            TimeSlot slot = new TimeSlot(segments[i].End, segments[i + 1].Start.Subtract(segments[i].End));
            segments.Insert(i + 1, slot);
            i++;
        }
    }

    for (int i = 0; i < segments.Count; i++)
    {
        Console.WriteLine("s: {0:mm':'ss}  d: {1:mm':'ss}  e: {2:mm':'ss}", segments[i].Start, segments[i].Span, segments[i].End);
    }
    Console.WriteLine();

    int lastIndex = segments.Count - 1;
    if (!segments[lastIndex].End.Equals(endTime))
    {
        TimeSlot lastSlot = new TimeSlot(segments[lastIndex].End, endTime.Subtract(segments[lastIndex].End));
        segments.Add(lastSlot);
    }

    for (int i = 0; i < segments.Count; i++)
    {
        Console.WriteLine("s: {0:mm':'ss}  d: {1:mm':'ss}  e: {2:mm':'ss}", segments[i].Start, segments[i].Span, segments[i].End);
    }
    Console.ReadKey();
}

which will provide this output:

s: 02:30  d: 01:13  e: 03:43
s: 04:25  d: 00:35  e: 05:00
s: 07:21  d: 02:34  e: 09:55

s: 00:00  d: 02:30  e: 02:30
s: 02:30  d: 01:13  e: 03:43
s: 04:25  d: 00:35  e: 05:00
s: 07:21  d: 02:34  e: 09:55

s: 00:00  d: 02:30  e: 02:30
s: 02:30  d: 01:13  e: 03:43
s: 03:43  d: 00:42  e: 04:25
s: 04:25  d: 00:35  e: 05:00
s: 05:00  d: 02:21  e: 07:21
s: 07:21  d: 02:34  e: 09:55

s: 00:00  d: 02:30  e: 02:30
s: 02:30  d: 01:13  e: 03:43
s: 03:43  d: 00:42  e: 04:25
s: 04:25  d: 00:35  e: 05:00
s: 05:00  d: 02:21  e: 07:21
s: 07:21  d: 02:34  e: 09:55
s: 09:55  d: 00:25  e: 10:20