Генерация подмассивов перекрывающихся диапазонов - PullRequest
Новая
       25

Генерация подмассивов перекрывающихся диапазонов

1 голос
/ 04 марта 2011

меня зовут Тимоти Сассон.Я работаю над разработкой некоторого программного обеспечения для планирования на C #, но столкнулся с некоторыми проблемами.Эта последняя часть программы предназначена для того, чтобы взять большой список еженедельных событий (сохраняемых как дни недели и время начала и окончания) и отсортировать их в подсписки, содержащие события, которые перекрываются друг с другом (таким образом, что никто не мог присутствовать на двух событиях в подсписке).

В настоящий момент он делает это, находя самое длинное событие в списке ((endTime-startTime) * numDays),и добавление его и каждого курса, с которым он пересекается, в подсписок.Затем он находит все «конфликты» (события, которые не перекрываются) и разрешает их, удаляя наименьшее количество возможных курсов.Это много, что у меня есть, но с количеством диапазонов, с которыми мне приходится иметь дело, я получаю довольно большое количество подсписков.Есть ли лучший способ разделить список, чтобы у меня было меньше подсписков?

Я рассмотрел метод грубой силы, просто пытался использовать любую возможность и идти с лучшим, но количестводиапазоны достаточно высоки (в среднем от 100 до 500), что может быть довольно медленным.Любые предложения или указатели будут наиболее признательны.

Спасибо за ваше время,

Тимоти Сассон

1 Ответ

0 голосов
/ 03 апреля 2011

Библиотека периодов времени для .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
...