Вычислить пересечение/пересечение между двумя списками, содержащими диапазоны

Я пытаюсь найти обратное пересечение, чтобы увидеть, могут ли две команды играть друг с другом, но мне трудно выяснить точный код для этого.

Класс, представляющий диапазоны ниже, будет содержать два свойства: время начала и время окончания, которые могут быть датой, временем или временным интервалом. У каждой команды может быть свой список. Свойство timepan сводится к минутам, поэтому 14:21 допустимо.

Команда 1 не может играть между двумя указанными периодами времени, поэтому она может играть только с 10:00 до 17:00. Однако мы сохраняем исключение.

Команда 2 может играть с 8:00 до 12:00.

Это означает, что команда 1 и команда 2 могут играть между 10-12. Есть ли хороший способ вычислить это в коде?

Команда 1

List<Restriction>
     Restriction
          StartTime: 8:00 AM
          EndTime: 10:00 AM
     Restriction
          StartTime: 5:00 PM
          EndTime: 9:00 PM

Команда 2

List<Restriction>
     Restriction
          StartTime: 12:00 PM
          EndTime: 9:00 PM

c# algorithm intercept intersection computation
person Mike Flynn    schedule 27.09.2014    source источник
comment
Извините, я запутался с обозначением времени.   -  person ziya    schedule 27.09.2014
comment
Просто печатаю здесь вслух, но я думаю, что вы могли бы превратить все часы дня в биты в массиве байтов, где игровые часы равны 1, а затем выполнить операцию И между командами. Что потрясает, так это то, что они могли играть друг с другом.   -  person Crowcoder    schedule 27.09.2014
comment
если вы конвертируете свое время в то, когда они могут играть (даже временно), а затем конвертируете его в набор доступных часов, это становится пересечением, а не обратным пересечением.   -  person Peter Ritchie    schedule 27.09.2014
comment
Мне нравится идея сравнения битов, но что, если вы можете перейти к минутам.   -  person Mike Flynn    schedule 27.09.2014

Ответы (1)


arrow_upward
1
arrow_downward

Создайте массив всех времен начала и окончания, включая +1 или -1, в зависимости от того, является ли каждый раз временем начала или окончания.

Для вашего набора времен это дает вам:

[(08:00, +1), (10:00, -1), (17:00, +1), (21:00, -1), (12:00, +1), (21:00, -1)]

Сортировать их:

[(08:00, +1), (10:00, -1), (12:00, +1), (17:00, +1), (21:00, -1), (21:00, -1)]

Сделайте текущую сумму плюс и минус 1:

[(08:00, 1), (10:00, 0), (12:00, 1), (17:00, 2), (21:00, 1), (21:00, 0)]

Текущая сумма — это количество команд (0, 1 или 2), которые заняты, начиная в это время. Таким образом, время, которое теперь помечено 0, является временем начала, когда обе команды свободны (здесь 10:00 и 21:00). Следующий раз в массиве - это конец бесплатного периода. Это дает периоды времени, когда обе команды свободны, включая периоды в начале и в конце (от -бесконечности до 08:00), (от 10:00 до 12:00) и (от 21:00 до +бесконечности).

person Paul Hankin    schedule 27.09.2014
comment
Интересный. Я попробую это. Выглядит именно то, что мне нужно, и никогда бы не подумал, если бы это. Как ты это придумал? - person Mike Flynn; 27.09.2014
comment
Как бы вы справились с двумя командами с 10:00 до 15:00 и с 12:00 до 9:00? Нужно ли включать бесконечность -10? - person Mike Flynn; 28.09.2014