Задача: 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⃣Используйте SortedSet<int>, чтобы автоматически сохранять отдельные элементы в отсортированном виде.

2⃣AddNum(value)— просто добавить элемент в SortedSet, дубликаты автоматически теряются.

3⃣GetIntervals()—
проходим поSortedSet
если текущий элемент продолжает текущий интервал ( value == right + 1) — расширение его
в противном случае сохраняем текущий интервал и начинаем новый
после цикла добавление последней интервала

😎 Решение:

using System;
using System.Collections.Generic;

public class SummaryRanges {
    private SortedSet<int> values;

    public SummaryRanges() {
        values = new SortedSet<int>();
    }

    public void AddNum(int value) {
        values.Add(value);
    }

    public List<int[]> GetIntervals() {
        var intervals = new List<int[]>();
        if (values.Count == 0) {
            return intervals;
        }

        int left = -1, right = -1;
        foreach (var value in values) {
            if (left < 0) {
                left = right = value;
            } else if (value == right + 1) {
                right = value;
            } else {
                intervals.Add(new int[] { left, right });
                left = right = value;
            }
        }
        intervals.Add(new int[] { left, right });
        return intervals;
    }
}

// Example usage
public class Program {
    public static void Main() {
        SummaryRanges sr = new SummaryRanges();
        sr.AddNum(1);
        sr.AddNum(3);
        sr.AddNum(7);
        sr.AddNum(2);
        sr.AddNum(6);
        List<int[]> intervals = sr.GetIntervals();
        foreach (var interval in intervals) {
            Console.WriteLine($"{interval[0]} {interval[1]}");
        }
    }
}

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