给定开始/结束时间数组的总空闲时间的算法

Question

假设您有开始和结束时间.

此外,您还会获得一系列作业,按其开始和结束时间进行描述.这些作业可能重叠(即,可以同时运行多个作业).我需要找到一种方法来确定空闲时间和未运行任何工作的时间.

当然,如果任何时候只能运行一个作业,我可以减去每个作业的运行时间,但重叠部分让我难过.

Answer 1

对时间进行排序,然后按顺序运行它们.
如果时间是开始时间,请将1添加到正在运行的任务中.
如果是停止时间,则减去1.
记录任务数为0时的时间.

Answer 2

将所有开始和结束时间放在一个数组中,将它们标记为开始或结束时间.按时间排序数组.现在遍历排序列表,计算正在运行的作业数量:

• 在读取开始时间时递增计数器
• 在读取结束时间时递减计数器

每当从0增加到1时,将(current_time - previous_time)添加到总空闲时间.如有必要,请记住特殊情况的开始和结束.