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

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

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

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

Пусть I1, I2............. In - обозначения интервалов в указанном порядке

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


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

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

  1. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  2. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  3. АЛГОРИТМ
  4. АЛГОРИТМ УДАЧИ
  5. Алгоритм исцеления:
  6. Алгоритм избавления от боли
  7. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  8. Алгоритм обработки результатов.
  9. 2. Специфика и алгоритмы работы с источниками.
  10. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
  11. Этапы социокультурного проектирования
  12. ЛЕКЦИЯ 18 3.2.2.2. Методы социокультурного проектирования
  13. Глава 3. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ПЕДАГОГИЧЕСКОГО ПРОЕКТИРОВАНИЯ
  14. 3.2.2. Социокультурная парадигма проектирования города Лекция 17
  15. Цели и задачи социокультурного проектирования.
  16. 6.4.2. Контролируемое проектирование