# Remove gaps between non-overlapping segments of an array of time elements

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.

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
}
}
``````
• Are you ordering by start or end time?
– Ewan
Commented Sep 24, 2016 at 20:13
• Do you want to add the time of the gap to the previous element? Why not just set the end-time of the previous element to the start time of the next element unless there's overlap? Commented Sep 24, 2016 at 22:40
• You are not telling what you want to do with the gaps. Don't make us reverse engineer your code to find out. Commented Sep 25, 2016 at 14:37
• each orange block is an array element (ordered by start time) which has a start and end time... some blocks overlap (in time) whereas others do not and there is a gap in time (the red line which indicates the duration), I would like to remove all the gaps (red lines) so that they butt up neatly together (but only the closest elements to the gap should align). Commented Sep 25, 2016 at 19:42

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.

• Thanks @Karl splitting this up for sure made it easier to tackle, have posted the code i used below. Commented Sep 29, 2016 at 22:55

Posting this as the code, @Karl helped me realise splitting this up made it much easier! SOLID principles enables much easier code.

``````List<Tuple<int, int>> FindGaps(List<LogEntry> entries)
{
var gaps = new List<Tuple<int, int>>();

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

var distanceForward = next.TimingsAbsolute.Start - current.TimingsAbsolute.End;

if (!(distanceForward > 0)) // there is no gap to the next element, continue
continue;

gaps.Add(new Tuple<int, int>(i, i+1)); // otherwise, we have found a gap...
}

return gaps;
}

List<Tuple<int, int>> FindContiguous(List<Tuple<int, int>> gaps, int totalLength)
{
var previous = 0;
var lastIndex = totalLength - 1;

var contiguous = new List<Tuple<int, int>>();

foreach (var gap in gaps)
{

previous = gap.Item2;
}

if (previous != lastIndex)
{
}

return contiguous;
}

List<LogEntry> RemoveGaps(List<LogEntry> entries, List<Tuple<int, int>> contiguous)
{
var newList = new List<LogEntry>();

var totalShift = 0.0;
LogEntry previousLast = null;

foreach (var seq in contiguous)
{
var startIndex = seq.Item1;
var endIndex = seq.Item2;

if (previousLast != null)
{
totalShift += entries[startIndex].TimingsAbsolute.Start - previousLast.TimingsAbsolute.End;
}

previousLast = entries[endIndex];

for (var i = startIndex; i <= endIndex; i++)
{
var entry = entries[i];

new LogEntry(
entry.Url,
entry.Status,
entry.TimeOffset-totalShift,
entry.Timings.Blocked,
entry.Timings.Dns,
entry.Timings.Connect,
entry.Timings.Ssl,
entry.Timings.Send,
entry.Timings.Wait,
entry.ConnectionId));
}
}

return newList;
}

public void Generate(List<LogEntry> entries, Guid testId)
{
// sort by time, lowest to highest
entries.Sort((a, b) => a.TimeOffset.CompareTo(b.TimeOffset));

// get a list of contigous elements
var contiguous = FindContiguous(FindGaps(entries), entries.Count);

// now remove the gaps between the contiguous sequences of elements
var list = RemoveGaps(entries, contiguous);
}
``````