算法找到的开始/结束时间总空闲时间给定的数组 [英] Algorithm for finding total idle time given array of start/end times

问题描述

说你给一个开始和结束的时间。

Say you're given a start and end time.

另外提供给您的是工作上的一个阵列，由他们开始和结束时间说明。这些工作可能会重叠（即有可能同时运行多个任务）。我需要找到一种方法来确定有多少时间花在闲置，没有运行任何作业。

Also you're given an array of jobs, described by their start and end times. These jobs may overlap (ie, there can be multiple jobs running at once). I need to find a way to determine how much time was spent idle and not running any job.

当然，如果只有一个任务可以在任何时候运行，我可能只是减去每个作业的运行时间，但重叠部分有我难住了。

Of course, if only one job can be running at any time, I could just subtract out the running times of each job, but the overlap part has me stumped.

推荐答案

把所有的开始和结束时间到了一个阵列，标记他们作为开始或结束时间。排序的数组的时间。现在通过排序列表循环，保持多少就业岗位正在运行的计数：

Put all the start and end times into a single array, tagging them as either start or end times. Sort the array by time. Now iterate through the sorted list, keeping a count of how many jobs are running by:

• 在读一开始的时候增加计数器
• 在读取结束时递减计数器

当你增加从零到一，加（CURRENT_TIME - previous_time）总空闲时间。请记住，还特别情况下，开始并在必要时结束。

Whenever you increment from zero to one, add (current_time - previous_time) to the total idle time. Remember to also special case the start and end if necessary.

这篇关于算法找到的开始/结束时间总空闲时间给定的数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！