给定开始/结束时间阵列找到总空闲时间的算法

Question

假设您给出开始和结束时间。

此外，您还可以获得一系列的工作，按其开始和结束时间描述。这些作业可能会重叠（即可能同时运行多个作业）。我需要找到一种方法来确定花了多少时间闲置和不运行任何工作。

当然，如果只有一个工作可以随时运行，我可以将每个工作的运行时间减去，但重叠部分让我难倒了。

Answer 1

把所有的开始和结束时间为一个单一的阵列，它们标记为无论是开始还是结束时间。按时间排序数组。现在，通过排序列表循环，保持多少作业运行的计数：

• 阅读的开始时间
• 当递减计数器读数的结束时间时增加计数器

每当您从零增加到1，将（current_time - previous_time）添加到总空闲时间。如有必要，还要记住特殊情况的开始和结束。

Answer 2

对时间进行排序，然后按顺序排列。
如果时间是开始时间，请将运行的任务数加1。
如果是停止时间，减去1
保持跟踪有多少时间时，任务数为0

Answer 3

这是一个稍微不同的方法。第一部分是为了说明的目的。

创建一个表示所有作业的完整时间轴的整数的数组。这可以在几小时，几分钟或任何你需要的。我会假设几个小时。查找最早的开始时间和最近的结束时间来设置数组的大小。初始化所有元素为零。

循环遍历每个作业，在作业正在运行的每个小时的时间轴上递增计数器。因此，如果一项工作从下午3点到下午5点运行，那就是两个小时，所以您应该增加3小时和4小时的时间段，以表明在这段时间内工作正在运行。

循环遍历时间轴，记录您遇到的零点数。那些是没有工作正在运行的时间段。

现在，如果你明白，摆脱阵列是相当容易的。而不是创建一个（大大小小的）数组，只需跟踪整个时间线的开始和结束时间。对于该范围内的每个小时，循环显示所有工作，并查看在此期间有多少人正在运行。任何零都是空闲时间。

Answer 4

Sort the jobs based on their end times. 

Jobs<startTime,EndTime>[] = contains the Sorted list. 

Take first Job in the list 
Jobs[0] 

intialize: 
    EndTime = Job[0].EndTime 
    StartTime = Job[0].StartTime 
    idleTime =0; 

For i = 1 till Jobs.size 
{ 
    if (Jobs[i].EndTime >= StartTime) 
    { 
     //Do nothing, its overlapping 
    } 
    else 
    { //Previoys Job time doesnot overlap, so get the idle time. 
     idleTime += (StartTime -Jobs[i].EndTime); 
    } 

    StartTime = Jobs[i].StartTime; 
    EndTime = Jobs[i].EndTime; 
} 

Answer 5

当有一个或多个作业正在运行时，您有大量的繁忙时间。 空闲时间是繁忙组块之间时间跨度的总和。 伪代码：

idle_time = 0 
sort jobs by start time 
foreach job in jobs 
{ 
    if (job.start > current_chunk.end) 
    { 
    idle_time += job.start - current_chunk.end 
    } 
    if (job.end > current_chunk.end) 
    { 
    current_chunk.end = job.end 
    } 
} 

注意：为了简单起见，我离开了的代码来处理第一个元素。