生成重叠范围的子数组

Question

我的名字是蒂莫西·萨松。我正在用 C# 开发一些调度软件，但遇到了一些麻烦。该程序的最后一部分旨在获取大量每周事件（存储为一周中的一天以及开始和结束时间），并将它们分类到包含彼此重叠的事件的子列表中（这样就没有人可能参加了子列表中的两项活动）。

目前，它通过在列表中查找“最长”事件 ((endTime-startTime)*numDays) 并将其及其重叠的每个课程添加到子列表中来实现此目的。然后，它会找到所有“冲突”（不重叠的事件）并解决它们，同时删除尽可能少的课程。我有这么多，但是由于我必须处理的范围数量，我最终得到了相当多的子列表。有没有更好的方法来分割列表，这样我最终会得到更少的子列表？

我考虑过一种蛮力方法，简单地尝试每种可能性并选择最好的，但范围的数量足够高（平均为 100-500），这样做可能会相当慢。任何建议或指示将不胜感激。

感谢您抽出宝贵时间，

蒂莫西·萨松

Answer 1

.NET 时间段库 http://www.codeproject .com/KB/datetime/TimePeriod.aspx 包含用于搜索重叠时间段的 TimePeriodIntersector。

通过对时间线上的所有时刻进行计数/排序，使用线性快速算法计算重叠。

TimePeriodIntersector 的用法如下所示：

// ----------------------------------------------------------------------
public void TimePeriodCombinerSample()
{
  TimePeriodCollection periods = new TimePeriodCollection();

  periods.Add( new TimeRange( new DateTime( 2011, 3, 01 ), new DateTime( 2011, 3, 10 ) ) );
  periods.Add( new TimeRange( new DateTime( 2011, 3, 04 ), new DateTime( 2011, 3, 08 ) ) );

  periods.Add( new TimeRange( new DateTime( 2011, 3, 15 ), new DateTime( 2011, 3, 18 ) ) );
  periods.Add( new TimeRange( new DateTime( 2011, 3, 18 ), new DateTime( 2011, 3, 22 ) ) );
  periods.Add( new TimeRange( new DateTime( 2011, 3, 20 ), new DateTime( 2011, 3, 24 ) ) );

  periods.Add( new TimeRange( new DateTime( 2011, 3, 26 ), new DateTime( 2011, 3, 30 ) ) );

  TimePeriodCombiner<TimeRange> periodCombiner = new TimePeriodCombiner<TimeRange>();
  ITimePeriodCollection combinedPeriods = periodCombiner.CombinePeriods( periods );

  foreach ( ITimePeriod combinedPeriod in combinedPeriods )
  {
    Console.WriteLine( "Combined Period: " + combinedPeriod );
  }
  // > Combined Period: 01.03.2011 - 10.03.2011 | 9.00:00
  // > Combined Period: 15.03.2011 - 24.03.2011 | 9.00:00
  // > Combined Period: 26.03.2011 - 30.03.2011 | 4.00:00
} // TimePeriodCombinerSample