DEV//UNIT
← Алгоритмыgreedy

Выбор активностей

Максимум непересекающихся интервалов: жадно по времени окончания.

время O(n log n)память O(1)уровень: начальный
Что происходит сейчас0/0
Нажмите Play, чтобы запустить сценарий
TypeScript — активная строка подсвечена шагом
1function maxActivities(intervals: Array<[s: number, e: number]>): number {
2  const sorted = [...intervals].sort((a, b) => a[1] - b[1])
3 
4  let count = 0
5  let lastEnd = -Infinity
6  for (const [start, end] of sorted) {
7    if (start >= lastEnd) {
8      count++
9      lastEnd = end // жадный выбор: раньше кончается — берём
10    }
11  }
12 
13  return count
14}

Проблема

Максимум непересекающихся интервалов: жадно по времени окончания.

Что вы видите

Сортируем по правому краю; каждая встреча, начинающаяся после прошлой — берём.

Как это работает

Обменный аргумент доказывает оптимальность: любой другой выбор можно перестроить в жадный без потерь. Канонический пример, где жадность строго лучше перебора.

Пошаговый разбор

  1. 01

    Сортировка

    По времени окончания.

  2. 02

    Совместимость

    Начало ≥ конец прошлой.

  3. 03

    Обменный аргумент

    Жадный = максимум.

Complexity и ограничения

time
O(n log n)
space
O(1)

Сложность см. в шапке страницы.

Edge cases

  • Пустой вход

    Корректная тривиальная обработка.

  • Вырожденный случай

    Минимум работы — сразу ответ.

Где встречается в реальности

Календарь

Расписание переговорок.

ЦП

Time-slotting задач.

Алокатор

Свободные диапазоны памяти.

Связанные алгоритмы

Топологическая сортировка
Shorts

«Максимум встреч в одном зале»

Тот же сценарий StepSequence в вертикальной композиции — с safe zones и записью WebM ниже на странице.

Shorts 9:16

Вертикальная композиция строится той же последовательностью шагов, что и страница: safe zones отмечены пунктиром (там живёт UI платформ), биты сценария подсвечиваются по прогрессу. Кнопка записи сохраняет WebM — детерминированная StepSequence даёт воспроизводимый ролик без монтажа.

Максимум встреч в одном зале
Нажмите Play
Бит 1/6 · 0–2 с
Hook
script-setup.ru/algorithms/activity-selection