有效的可用时间查找器

Question

我在特定工作日的一组约会，从上午8点到下午6点：

约会1：9 am-11am约会2：2 pm-5pm

我正在寻找一种找到空闲时间的有效方法。因此，在这种情况下，可用时间为：

8 am-9am上午11点至下午2点5 pm-6pm

所以我有一个TimeBlock类

class TimeBlock {
  public DateTime start
  public DateTime end
}

var appointments = new List<TimeBlock>();
var freeTimeBlocks = new List<TimeBlock>();

' add appointments
appointments.Add(new TimeBlock{start...
appointments.Add(new TimeBlock{start...

我正在寻找一种找到空闲时间的有效方法，因为该算法将在相当大的数据集上运行。

Answer 1

尝试一下，它假定没有重叠的约会：

var orderedAppointments = appointments.OrderBy(a => a.start).ToArray();

freeTimeBlocks.Clear();

for(int i = 0; i < orderedAppointments.Length - 1; i++)
{
    freeTimeBlocks.Add(new TimeBlock(){ start = orderedAppointments[i].end; end = orderedAppointments[i + 1].start });
}
var firstAppointment = orderedAppointments.First();
var lastAppointment = orderedAppointments.Last();

if(firstAppointment.start.Hour > 8)
   freeTimeBlocks.Add(new TimeBlock() { start = firstAppointment.Today.AddHours(8); end = firstAppointment.start });
if(lastAppointment.end.Hour < 18)
   freeTimeBlocks.Add(new TimeBlock() { start = lastAppointment.end; end = lastAppointment.Today.AddHours(18) });

Answer 2

确保对时间段进行排序（O(nlogn)或更好），然后遍历它们，并创建从每个块的末尾到下一个块的开始（O(n)）的可用性范围。

Answer 3

我认为这种方法对于大数据集（d * u >> n）渐近非常有效，只要它们可以容纳在内存中：

如果天数为d，用户数为u，每位用户每天的平均约会数为n，则为O（d * u * n），而基于排序的单日方法为更像O（d * u * n * log n）。

（（如果u = 1或d = 1，没关系-没关系。）

1. 创建由所有可能的时隙。例如，如果每5个时隙分钟，您将拥有一系列大小为120。此步骤为O（1）。我们假设可能的时隙数是固定的，因此它与复杂度分析无关。

2. 通过all个约会，为all天和all个用户，并将约会（连同该日期和用户的记录）添加到相应的约会开始和约会结束时间的列表。如果您使用链接列表并将其每次添加到列表的开头，则此步骤为O（d * u * n）。

3. 创建一个数组来记录每天和每个用户的“当前”空闲时间-您将在下一步中了解其工作原理。
4. 遍历第一个数组，并对该数组中的每个列表循环遍历该列表（因此，循环是嵌套的）。对于每个约会，您看到的都是“立即结束约会”，请在该时间针对该天和该用户开始记录一个新的空闲时段。对于每个约会，您都会看到这是一个“立即开始约会”，请完成该天和用户（如果有）的空闲时间记录，如果持续时间为零，则将其丢弃-如果没有，并且不是上午8点，则创建一。此步骤也是O（d * u * n）。
5. 填写下午6点的所有空闲时间记录。此步骤是最坏的情况O（d * u）。

无需进行约会间比较或搜索！

这基于基数排序。

但是，我不确定这是否会更好[[在实践中

。当然需要更多空间！

Answer 4

Answer 5

我认为这可以做得更优雅，但我不知道如何完成。