Какое минимальное количество дней требуется для проведения этой конференции?

Я специалист по ИТ/математике, помогающий организовать конференцию. Время (но не дни) для событий во время конференции заданы в камне. Например, мы знаем, что какое-то событие произойдет с 13:00 до 15:00. Я пытаюсь написать сценарий, который определяет наименьшее количество дней, в течение которых мы можем запускать конференцию и не иметь перекрывающихся событий.

Все события происходят в течение дня; никакое событие не имеет времени, которое пересекает 12am или охватывает несколько дней.

Мой первый выстрел по этому вопросу включал в себя моделирование его как неориентированного графа. Мы можем представить события в виде вершин, а ребро между двумя вершинами означает, что два события перекрываются. Затем проблема сводится к нахождению минимального хроматического числа графика - наименьшее количество цветов, которое требуется для окраски вершин, гарантируя, что конечные точки каждого ребра отличаются по цвету.

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

Любые другие лидеры? Это похоже на NP-полную проблему, но я уверен, мы сможем решить ее в полиномиальное время с умным компромиссом во времени, то есть с динамическим программированием.

2 ответа

Поскольку ваш график является интервальным графиком, задачу гораздо проще решить тогда для общих графиков с использованием алгоритма линии развертки. Пусть говорят, что ваши события представлены в виде кортежей (s_i, f_i), где s_i - время начала события, а f_i - время окончания (оба в часах).

Затем вы можете использовать следующий алгоритм:

events := union of {(f_i, -1), (s_i, 1)} for all i
sort events lexicographically
answer := 0
count := 0
for (time, c) in events:
 count += c
 answer := max(answer, count)

return answer

Сложность времени: O(n log n) или даже O(n) если мы предполагаем ограниченное число возможных времен (что, вероятно, будет иметь место на практике).


Это не проблема NP, с точки зрения графиков - это критический путь, но я не вижу упоминания о том, что события связаны друг с другом (т.е. порядок событий не определен), чтобы решить эту проблему

  1. создать массив с 24 часами [0-23] (0 инициализировано)
  2. пройдите через все события и добавьте добавление 1 к каждому часу, который он занят (для события с 13:00 до 15:00 - добавьте только 13 и 14)
  3. найти максимальное количество в массиве - это даст вам, сколько событий на самом деле перекрывается временем, так что это минимальная продолжительность конференции (максимум можно найти на втором этапе)

Итак, на самом деле это проблема O (N)

licensed under cc by-sa 3.0 with attribution.