Задача: 352. Data Stream as Disjoint Intervals
Сложность: hard

Дано поступление данных из последовательности неотрицательных целых чисел a1, a2, ..., an, необходимо обобщить увиденные числа в виде списка непересекающихся интервалов.
Реализуйте класс SummaryRanges:
SummaryRanges() Инициализирует объект с пустым потоком.
void addNum(int value) Добавляет целое число в поток.
int[][] getIntervals() Возвращает обобщение текущих чисел в потоке в виде списка непересекающихся интервалов [starti, endi]. Ответ должен быть отсортирован по starti.

Пример:

Input
["SummaryRanges", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals"]
[[], [1], [], [3], [], [7], [], [2], [], [6], []]
Output
[null, null, [[1, 1]], null, [[1, 1], [3, 3]], null, [[1, 1], [3, 3], [7, 7]], null, [[1, 3], [7, 7]], null, [[1, 3], [6, 7]]]

👨‍💻 Алгоритм:

1⃣Инициализировать структуру данных TreeSet для хранения значений.

2⃣addNum(int value)
Просто добавить value в values. Если эквивалент TreeSet вашего языка программирования позволяет дублировать значения, как например SortedList в Python, нужно также проверить, что value не существует в values, так как дубликаты нарушат алгоритм.

3⃣getIntervals
Если values пуст, вернуть пустой массив.
Создать пустой список интервалов.
Установить left = right = -1. left представляет левую границу текущего интервала, а right представляет правую границу.
Итерировать по values. На каждой итерации:
Если left < 0, установить left = right = value.
Иначе, если value = right + 1, установить right = value, так как мы можем продолжить текущий интервал.
Иначе, мы не можем продолжить текущий интервал. Вставить [left, right] в intervals и установить left = right = value для начала нового интервала.
Вставить [left, right] в intervals и вернуть intervals.

😎 Решение:

class SummaryRanges {
    private $values;

    public function __construct() {
        $this->values = [];
    }

    public function addNum($value) {
        $this->values[$value] = true;
    }

    public function getIntervals() {
        if (empty($this->values)) {
            return [];
        }

        $sortedValues = array_keys($this->values);
        sort($sortedValues);

        $intervals = [];
        $left = -1;
        $right = -1;

        foreach ($sortedValues as $value) {
            if ($left < 0) {
                $left = $right = $value;
            } elseif ($value == $right + 1) {
                $right = $value;
            } else {
                $intervals[] = [$left, $right];
                $left = $right = $value;
            }
        }

        $intervals[] = [$left, $right];
        return $intervals;
    }
}

// Example usage
$sr = new SummaryRanges();
$sr->addNum(1);
$sr->addNum(3);
$sr->addNum(7);
$sr->addNum(2);
$sr->addNum(6);
$intervals = $sr->getIntervals();
foreach ($intervals as $interval) {
    echo $interval[0] . " " . $interval[1] . "\n";
}
?>

Ставь 👍 и забирай 📚 Базу знаний