计算同时运行的最大作业的最佳方法

Question

我必须根据开始时间和结束时间创建计算同时运行的最大作业数的报告。

例如，我可能有这样的数据:

var jobs = new[]
{
new { Id = 1, Start = TimeSpan.Parse("10:00"), End = TimeSpan.Parse("10:30") },
new { Id = 2, Start = TimeSpan.Parse("10:20"), End = TimeSpan.Parse("11:00") },
new { Id = 3, Start = TimeSpan.Parse("10:40"), End = TimeSpan.Parse("10:50") },
new { Id = 4, Start = TimeSpan.Parse("11:10"), End = TimeSpan.Parse("11:30") },
};

所以max count应该是2，因为"重叠"作业只有1&2和2&3

最好的分析方法是什么?

Answer 1

画如下图中的句号:

09:50 
10:00 |
10:10 |
10:20 | |
10:30 | |
10:40   | |
10:50   | |
11:00   |
11:10       |
11:20       |
11:30       |
11:40

想象你移动这幅画的水平线。您可以使用计数器，当线越过周期的开始时，该计数器增加，当线越过周期的结束时，该计数器减少。计数器的最大值是您需要的结果。

我们需要准备数据来实现算法。

var points = new List<(TimeSpan, bool)>();
foreach (var job in jobs)
{
points.Add(job.Start, true);
points.Add(job.End, false);
}
points = points.OrderBy(x => x.Item1)
.ToList();

现在我们可以计算竖线的最大值了

int count = 0;
int max = 0;
foreach (var point in points)
{
if (point.Item2)
{
count++;
if (count > max)
max = count;
}
else
count--;
}

Answer 2

看起来很直接。

var jobs = new[]
{
new { Id = 1, Start = TimeSpan.Parse("10:00"), End = TimeSpan.Parse("10:30") },
new { Id = 2, Start = TimeSpan.Parse("10:20"), End = TimeSpan.Parse("11:00") },
new { Id = 3, Start = TimeSpan.Parse("10:40"), End = TimeSpan.Parse("10:50") },
new { Id = 4, Start = TimeSpan.Parse("11:10"), End = TimeSpan.Parse("11:30") },
};
var events =
from j in jobs
from e in new []
{
new { Timestamp = j.Start, Value = 1, },
new { Timestamp = j.End, Value = -1, },
}
orderby e.Timestamp, e.Value
select e.Value;

int a = 0;
int max = 0;
foreach (var e in events)
{
a += e;
max = max > a ? max : a;
}

我得到2

现在，它可以稍微改进微软的System.InteractiveNuGet库。

int max = events.Scan(0, (a, x) => a + x).Max();