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

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") },
};

所以最大计数应该是 2，因为 'overlapping' 作业只有 1&2 和 2&3

最好的分析方法是什么？

Answer 1

看起来很简单。这对我有用：

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。

现在，可以使用 Microsoft 的 System.Interactive NuGet 库稍微改进它。

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

Answer 2

像下面这样画周期：

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--;
}

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

Best way to calculate max jobs run simultaneously

c#

algorithm

reporting

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

Best way to calculate max jobs run simultaneously

c#

algorithm

reporting

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