Задача: 57. Insert Interval
Сложность: medium

Дан массив intervals, содержащий непересекающиеся интервалы, отсортированные по start. Дано newInterval = [start, end].

Нужно вставить newInterval так, чтобы intervals оставался отсортированным и не имел пересекающихся интервалов.

Пример:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]  
Output: [[1,5],[6,9]]  

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

1⃣Добавить в результат все интервалы, которые переходят к новому интервалу и не пересекаются с ними.

2⃣Объединить все пересекающиеся интервалы с newInterval в один.

3⃣Добавить функциональные интервалы без изменений.

😎 Решение:

public class Solution {
    public int[][] Insert(int[][] intervals, int[] newInterval) {
        int n = intervals.Length, i = 0;
        List<int[]> res = new List<int[]>();

        while (i < n && intervals[i][1] < newInterval[0]) {
            res.Add(intervals[i]);
            i++;
        }

        while (i < n && newInterval[1] >= intervals[i][0]) {
            newInterval[0] = Math.Min(newInterval[0], intervals[i][0]);
            newInterval[1] = Math.Max(newInterval[1], intervals[i][1]);
            i++;
        }

        res.Add(newInterval);

        while (i < n) {
            res.Add(intervals[i]);
            i++;
        }

        return res.ToArray();
    }
}

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