patterncsharpMinor

Optimizing timeline generation

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

timelinegenerationoptimizing

Problem

I have a bunch of processes that are being executed on different virtual machines. All of those processes have a StartDate, EndDate and Resource properties. Resource is a specific virtual machine it was ran on. I generated the actual timeline for items and found out that all of those resources have "holes" in timeline that could fit other processes running on other machines at the same time, which means I could live with less machines. So I am now trying to come up with an algorithm that tries to fit all those processes to timeline. It adds a timeline and first item to timeline, for every next item, it checks if the EndDate of the last item in timeline is greater than current items StartDate, if so Add a new timeline, else put to existing timeline. The current implementation:

```
public List GetOptimizedTimeline()
{
var allItems = GetInterestingItems().OrderBy(x => x.StartDate).ToList();
if (!allItems.Any())
{
return null;
}
// Add the first item to first resource
var firstitem = allItems.FirstOrDefault();
var timelineCount = 1;
var timeline = new List
{
new TimelineDto
{
itemId = firstitem.Id,
Resource = timelineCount.ToString(),
StartTime = firstitem.StartDate,
EndTime = firstitem.EndDate
}
};
allItems.Remove(firstitem);

foreach (var item in allItems)
{
var added = false;
for (var i = 1; i x.Resource.Equals(i.ToString()));
if (item.StartDate > last.EndTime)
{
// Add to existing
timeline.Add(new TimelineDto
{
itemId = item.Id,
Resource = i.ToString(),
StartTime = item.StartDate,
EndTime = item.EndDate
});
added = true;
break;
}
}
// suitable resource already found, cool.
if

Solution

Compound words like firstitem should be camelCase.

Why is the Resource property of TimelineDto a string, when you seem to be filling it with ints?

allItems is a bad name, item is even worse. I have no idea what this represents.

I also have to object to TimelineDto, especially when timeline = new List.

var firstitem = allItems.FirstOrDefault(); can return a null, yet you never check this.

Why are you even using the OrDefault version, considering that the first line sorts the result of GetInterestingItems() by StartDate, which would throw an exception if one of the items was null.

Is there a point to all of this:

// Add the first item to first resource
var firstitem = allItems.FirstOrDefault();
var timelineCount = 1;
var timeline = new List
{
    new TimelineDto
    {
        itemId = firstitem.Id,
        Resource = timelineCount.ToString(),
        StartTime = firstitem.StartDate,
        EndTime = firstitem.EndDate
    }
};
allItems.Remove(firstitem);

Except for var timelineCount = 1; I don't see how this isn't handled by the logic inside foreach (var item in allItems). Of course you need to rethink var last = timeline.Last(x => x.Resource.Equals(i.ToString())); and if (item.StartDate > last.EndTime), but that seems a more elegant solution than the 10+ lines required to add a first entry to timeline.

This code is repeated three times, so it should be moved to a method:

new TimelineDto
{
    itemId = item.Id,
    Resource = timelineCount.ToString(),
    StartTime = item.StartDate,
    EndTime = item.EndDate
}

WRT your question, I don't see how you can parallelize it without running the risk of duplicate entries.

I do wonder whether it wouldn't be easier (and increase performance) to maintain a Dictionary instead of doing var last = timeline.Last(x => x.Resource.Equals(i.ToString())); each time. Key of that dictionary is the Resource, value is the EndTime.

So you'd end up with something like this:

public List GetOptimizedTimeline()
{
    var items = GetInterestingItems().OrderBy(x => x.StartDate).ToList();
    if (!items.Any())
    {
        return null;
    }

    var timeline = new List();
    var endTimeByResource = new Dictionary();
    var timelineCount = 1;

    foreach (var item in items)
    {
        var added = false;
        for (var i = 1; i  endTime)
                {
                    timeline.Add(CreateTimelineDto(item, i));
                    endTimeByResource[i] = item.EndTime;
                    added = true;
                    break;
                }
            }
        }

        if (added)
            continue;

        timelineCount++;
        timeline.Add(CreateTimelineDto(item, i));
        endTimeByResource[i] = item.EndTime;
    }

    return timeline;
}

Beware: I have not tested this code, so there might be some part of the logic missing! I suspect the if(endTimeByResource.TryGetValue(i, out endTime) needs an else where you add a new TimelineDto.

I would even consider getting rid of timelineCount completely and instead do for (var i = 1; i <= endTimeByResource.Keys.Count; i++), that way you might even be able to get rid of added, something like this:

foreach (var item in items)
{
    for (var i = 1; i  endTime)
            {
                timeline.Add(CreateTimelineDto(item, i));
                endTimeByResource[i] = item.EndTime;
                break;
            }
        }
    }
}

Again: this is untested.

I think it can even be reduced to this:

for (var i = 1; i  endTime)
        {
            timeline.Add(CreateTimelineDto(item, i));
            endTimeByResource[i] = item.EndTime;
            break;
        }
    }

Code Snippets

// Add the first item to first resource
var firstitem = allItems.FirstOrDefault();
var timelineCount = 1;
var timeline = new List<TimelineDto>
{
    new TimelineDto
    {
        itemId = firstitem.Id,
        Resource = timelineCount.ToString(),
        StartTime = firstitem.StartDate,
        EndTime = firstitem.EndDate
    }
};
allItems.Remove(firstitem);

new TimelineDto
{
    itemId = item.Id,
    Resource = timelineCount.ToString(),
    StartTime = item.StartDate,
    EndTime = item.EndDate
}

public List<TimelineDto> GetOptimizedTimeline()
{
    var items = GetInterestingItems().OrderBy(x => x.StartDate).ToList();
    if (!items.Any())
    {
        return null;
    }

    var timeline = new List<TimelineDto>();
    var endTimeByResource = new Dictionary<int, DateTime>();
    var timelineCount = 1;

    foreach (var item in items)
    {
        var added = false;
        for (var i = 1; i <= timelineCount; i++)
        {
            DateTime endTime;
            if(endTimeByResource.TryGetValue(i, out endTime)
            {
                if (item.StartDate > endTime)
                {
                    timeline.Add(CreateTimelineDto(item, i));
                    endTimeByResource[i] = item.EndTime;
                    added = true;
                    break;
                }
            }
        }

        if (added)
            continue;

        timelineCount++;
        timeline.Add(CreateTimelineDto(item, i));
        endTimeByResource[i] = item.EndTime;
    }

    return timeline;
}

foreach (var item in items)
{
    for (var i = 1; i <= endTimeByResource.Keys.Count; i++)
    {
        DateTime endTime;
        if(endTimeByResource.TryGetValue(i, out endTime)
        {
            if (item.StartDate > endTime)
            {
                timeline.Add(CreateTimelineDto(item, i));
                endTimeByResource[i] = item.EndTime;
                break;
            }
        }
    }
}

for (var i = 1; i <= endTimeByResource.Keys.Count; i++)
    {
        DateTime endTime;
        endTimeByResource.TryGetValue(i, out endTime);

        if (item.StartDate > endTime)
        {
            timeline.Add(CreateTimelineDto(item, i));
            endTimeByResource[i] = item.EndTime;
            break;
        }
    }

Context

StackExchange Code Review Q#122349, answer score: 7

Revisions (0)

No revisions yet.