Есть конечное число каких-то абстрактных задач (к примеру, это таски, назначенные на сегодня одному из специалистов в системе сервис-деск). Каждая задача имеет четко установленное время начала и время окончания. Это время задается с интервалом, скажем, 30 минут. Задачи пересекаются, то есть допускается ситуация, когда с 11:30 до 12:00 запланировано выполнение трех разных задач.
Необходимо нарисовать табличку, где строки - это время, а колонки - задачи. Иллюстрация ниже поможет понять принцип.
Интересный момент вот в чем: каждая задача стремится занять все доступные колонки.
Если задача не пересекается ни с одной другой задачей - она займет n = 6 колонок (задача A).
Если задача пересекается с еще одной задачей и только с ней - каждая займет n/2=3 колонки (задачи G и H).
При этом, если одна из задач уже занимает m=2 колонок, то другая должна занять n-m=4 колонки (задачи E и F).
Вопросы, которые необходимо решить:
1) заранее узнать общее количество колонок n
2) какую задачу в каких колонках размещать
Специально не буду описывать тот подход, который я уже опробовал, дабы не вводить никого в заблуждение :)
Он очень наивен и хорошо работает только на простейших примерах. Возможно, расскажу потом.
Подозреваю, что в целом задача сводится к максимально "плотному" размещению отрезков без пересечений на нескольких осях. Реализовав подобный алгоритм, я смогу решить сразу две подзадачи - узнать количество колонок n и принадлежность задач колонкам.
Есть идеи? Куда смотреть?
Средний