Optimizing timeline generation 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&lt;TimelineDto&gt; GetOptimizedTimeline()
{
    var allItems = GetInterestingItems().OrderBy(x =&gt; 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&lt;TimelineDto&gt;
    {
        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 &lt;= timelineCount; i++)
        {
            // as items are ordered by date, take the last item in current resource and see if the new items "fits" to that resource
            var last = timeline.Last(x =&gt; x.Resource.Equals(i.ToString()));
            if (item.StartDate &gt; 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 (added)
            continue;
        // Current item did not fit into any existing resource, add a new one. 
        timelineCount++;
        timeline.Add(new TimelineDto
        {
            itemId = item.Id,
            Resource = timelineCount.ToString(),
            StartTime = item.StartDate,
            EndTime = item.EndDate
        });
    }
    return timeline;
}


Now this does what I need, but for 100k items it takes minutes to complete. I am processing 1M items daily so it's not that I can't wait several minutes, but it would be great to optimize it. Can I parallelize this?
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&lt;TimelineDto&gt;. 



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&lt;TimelineDto&gt;
{
    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 =&gt; x.Resource.Equals(i.ToString())); and if (item.StartDate &gt; 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&lt;int, DateTime&gt; instead of doing var last = timeline.Last(x =&gt; 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&lt;TimelineDto&gt; GetOptimizedTimeline()
{
    var items = GetInterestingItems().OrderBy(x =&gt; x.StartDate).ToList();
    if (!items.Any())
    {
        return null;
    }

    var timeline = new List&lt;TimelineDto&gt;();
    var endTimeByResource = new Dictionary&lt;int, DateTime&gt;();
    var timelineCount = 1;

    foreach (var item in items)
    {
        var added = false;
        for (var i = 1; i &lt;= timelineCount; i++)
        {
            DateTime endTime;
            if(endTimeByResource.TryGetValue(i, out endTime)
            {
                if (item.StartDate &gt; 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 &lt;= 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 &lt;= endTimeByResource.Keys.Count; i++)
    {
        DateTime endTime;
        if(endTimeByResource.TryGetValue(i, out endTime)
        {
            if (item.StartDate &gt; 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 &lt;= endTimeByResource.Keys.Count; i++)
    {
        DateTime endTime;
        endTimeByResource.TryGetValue(i, out endTime);

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