C# Algorithms – Removing Gaps Between Non-Overlapping Segments of an Array of Time Elements

algorithmscsorting

I have an array of elements, each with a start time and an end time.

These form a timeline, some of which overlap, and others that do not (and have a gap between groups of overlapping elements).

I written some code that removes the gaps between the non-overlapping elements (red lines as per the image below) however it is starting to get messy and not catching edge cases.

red gaps

Does an algorithm exist already that will remove the red gaps and shift everything up neatly?

My code stab is below:

// sort by time, lowest to highest
entries.Sort((a, b) => a.TimeOffset.CompareTo(b.TimeOffset));

var lookingForFirstGap = true;
var storedOffset = 0.0;
var indexToTrimFrom = 0;

for (var i = 0; i < entries.Count -1; i++ )
{
    // var previous = entries[i-1];
    var current = entries[i];
    var next = entries[i+1];

    // var distanceBack = previous.TimingsAbsolute.End - current.TimingsAbsolute.Start;
    var distanceForward = next.TimingsAbsolute.Start - current.TimingsAbsolute.End;

    Console.WriteLine("Distance {0} -> {1} is {2}", i, i+1, distanceForward);

    if (!(distanceForward > 0))
        continue;

    if (lookingForFirstGap)
    {
        indexToTrimFrom = i + 1;
        Console.WriteLine("To trim from " + indexToTrimFrom);
        storedOffset = distanceForward; // we have found a gap, store the amount
        lookingForFirstGap = false; // now start looking for element where there is a gap after it
    }
    else
    {
        var indexToTrimTo = i;

        for (var x = indexToTrimFrom; x <= indexToTrimTo; x++)
        {
            // trim all
            Console.WriteLine("Adjust [" + x + "] by " + storedOffset);
        }

        if (distanceForward > 0)
        {
            indexToTrimFrom = i + 1;
            Console.WriteLine("To trim from " + indexToTrimFrom);
            storedOffset = distanceForward; // we have found a gap, store the amount
        }
        else
            lookingForFirstGap = true; // start looking for gap again
    }
}

Best Answer

You're trying to do too much in one loop. Subtracting the gaps is difficult because it's difficult to identify the gaps. Identifying the gaps is difficult because of all the weird ways the intervals overlap, so remove the overlapping interval problem first.

Make one pass to flatten the intervals, using an algorithm from this question. Then one pass to make a list of gaps, which should be very simple with the flattened list.

Now you're ready to loop through your original list of intervals. For each interval, see how many gaps occur before it, and subtract the cumulative time of each.

Related Topic