Проектирование алгоритма

Пусть d — глубина множества интервалов; каждому интервалу будет назначена метка из множества чисел {1, 2, ..., d} так, чтобы перекрывающиеся интервалы по- мечались разными числами. Так мы получим нужное решение, поскольку каждое число может интерпретироваться как имя ресурса, а метка каждого интервала — как имя ресурса, которому он будет назначен.

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

Отсортировать интервалы по начальному времени, с произвольным порядком совпадений

Пусть I₁, I₂............. I_n - обозначения интервалов в указанном порядке

Для j = 1,2,3............... n

<< | >>

↑

Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Проектирование алгоритма:

- Windows - Архитектура компьютера - Интернет - Информатика - Компьютер - Компьютерные и телекоммуникационные системы - Программирование - Социальные сети -

- Английский язык - Астрология - Астрономия - Биология - Военная литература - Журналистика - Компьютерная инженерия - Педагогика - Право - Психология - Социология -