6. Interval Scheduling

«Чтобы успеть сделать как можно больше дел, беритесь за то, что освободит вас раньше всего».
— Чарльз Энтони Ричард Хоар

Планирование интервалов: Максимизация пропускной способности

Задача Interval Scheduling (планирование непересекающихся интервалов) — канонический фундамент жадных алгоритмов, лежащий в основе LeetCode №435 и №452.

Формулировка: Задан набор интервалов $[start, end]$. Требуется выбрать максимальное количество взаимно непересекающихся интервалов.

В бэкенде эта математическая модель управляет распределением CPU-квантов в планировщиках, шардированием временных рядов (Time-series data) в TSDB (Prometheus, InfluxDB), блокировками коммит-окон в базах данных и алгоритмами очистки устаревших сессий (TTL eviction).

Ключевой инсайт: Сортировка по времени окончания

Частая ошибка начинающих разработчиков — сортировка интервалов по времени начала (Start).
Контрпример: интервал $[0, 100]$ начинается раньше всех. Если выбрать его, он заблокирует все остальные встречи на целый день. При этом два коротких интервала $[1, 2]$ и $[3, 4]$ позволяют провести вдвое больше встреч.

Жадный инвариант:
Мы обязаны сортировать интервалы по времени окончания (End). Освобождая ресурс как можно раньше, мы оставляем максимально возможное окно для всех последующих интервалов (принцип Greedy Stays Ahead).

flowchart TD
    classDef process fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef success fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
    classDef error   fill:#7f1d1d,stroke:#f87171,stroke-width:1px,color:#f8fafc
    classDef warning fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
    classDef entry   fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc

    A["Сортировка по End (возрастание)"]:::entry --> B["Берем первый интервал<br>lastEnd = intervals[0].End"]:::process
    B --> C{"intervals[i].Start >= lastEnd?"}:::warning
    C -->|"Да: Нет пересечения"| D["Берем интервал: count++<br>lastEnd = intervals[i].End"]:::success
    C -->|"Нет: Конфликт"| E["Пропускаем интервал<br>lastEnd не меняется"]:::error
    D --> Next{"Есть еще интервалы?"}:::warning
    E --> Next
    Next -->|"Да"| C
    Next -->|"Нет"| Finish["Возврат count"]:::success
  

Идиоматичная реализация на Go

package main

import (
    "cmp"
    "slices"
)

type Interval struct {
    Start int
    End   int
}

// maxNonOverlappingIntervals возвращает максимальное число непересекающихся интервалов.
func maxNonOverlappingIntervals(intervals []Interval) int {
    if len(intervals) <= 1 {
        return len(intervals)
    }

    // Сортируем по правому краю (End) через дженерик cmp.Compare
    slices.SortFunc(intervals, func(a, b Interval) int {
        return cmp.Compare(a.End, b.End)
    })

    count := 1
    lastEnd := intervals[0].End

    for i := 1; i < len(intervals); i++ {
        if intervals[i].Start >= lastEnd {
            count++
            lastEnd = intervals[i].End
        }
    }

    return count
}

Резюме

1. Критерий жадности: Сортировка по End — единственно верный критерий максимизации количества непересекающихся интервалов.
2. Безопасность типов: Использование cmp.Compare защищает от целочисленного переполнения при вычитании больших временных меток.
3. Локальность данных: Передавайте интервалы структурами по значению для ускорения сортировки и обхода.

В следующей статье мы рассмотрим инверсию этой задачи — минимизацию удаляемых отрезков: 7. Non-overlapping Intervals.