Вставить интервал

Постановка задачи

Вам дан массив непересекающихся интервалов intervals, где intervals[i] = [starti, endi] представляют начало и конец интервала ith, а intervals отсортированы в порядке возрастания по starti. Вам также дан интервал newInterval = [start, end], представляющий начало и конец другого интервала.

Вставьте newInterval в intervals так, чтобы intervals по-прежнему сортировалось в порядке возрастания по starti, а intervals по-прежнему не имело перекрывающихся интервалов (при необходимости объедините перекрывающиеся интервалы).

Вернуть intervals после вставки.

Постановка задачи взята с: https://leetcode.com/problems/insert-interval.

Пример 1:

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

Пример 2:

Input: intervals = [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], newInterval = [4, 8]
Output: [[1, 2], [3, 10], [12, 16]]
Explanation: Because the new interval [4, 8] overlaps with [3, 5], [6, 7], [8, 10].

Ограничения:

- 0 <= intervals.length <= 10^4
- intervals[i].length == 2
- 0 <= starti <= endi <= 10^5
- intervals is sorted by starti in ascending order.
- newInterval.length == 2
- 0 <= start <= end <= 10^5

Решения для вставки интервала

Подход 1: обрабатывать все случаи

При работе над такого рода проблемами мы сначала рассматриваем все случаи, которые нам необходимо обработать при вставке нового интервала. Вот пять случаев, которые нам нужно обработать в нашем коде:

Предположим, что новый интервал, который вставляется, равен [a, b].

1. Случай 1: b ‹ начальное значение первого интервала в списке
   Вставьте интервал в начало списка.
2. Вариант 2: конечное значение последнего интервала в списке ‹ a
   Вставить интервал в конец списка
3. Случай 3: a ‹ (начальное значение первого интервала) и b › (конечное значение последнего интервала)
   Новый интервал является надмножеством этого списка. Он содержит все интервалы списка. В результате мы возвращаем новый интервал.
4. Случай 4: Новый интервал попадает между любыми двумя интервалами в списке и не перекрывается ни с одним интервалом.
   Мы просто вставляем интервал в правильное положение в списке. Например.

Input: List : [23, 46], [49, 65], [100, 120] 
New interval : [70, 89] 
Output: [23, 46], [49, 65], [70, 89], [100, 120]

5. Случай 5: Когда новый интервал перекрывается с интервалами списка
Мы объединяем новый интервал с перекрывающимися интервалами. Чтобы понять этот случай, обратитесь к предыдущему блогу Интервалы слияния.

Фрагмент C++ этого подхода выглядит следующим образом:

vector<vector<int>> insertNewInterval (vector<vector<int>>& intervals, interval newInterval) {
    vector<vector<int>> result;
    int n = intervals.size();

    // if the set is empty, then simply insert newInterval and return.
    if (n == 0) {
        result.push_back(newInterval);
        return result;
    }

    // case 1 and case 2 (new interval is not overlapping with any interval)
    if (newInterval[1] < intervals[0][0] || newInterval[0] > intervals[n - 1][1]) {
        if (newInterval[1] < intervals[0][0])
            result.push_back(newInterval);

        for (int i = 0; i < n; i++)
            result.push_back(intervals[i]);

        if (newInterval[0] > intervals[n - 1][1])
            result.push_back(newInterval);

        return result;
    }

    // case 3 (New interval covers all existing)
    if (newInterval[0] <= intervals[0][0] && newInterval[1] >= intervals[n - 1][1]) {
        result.push_back(newInterval);
        return result;
    }

    // case 4 and case 5
    // Two cases need to check whether intervals overlap or not.
    bool overlap = true;

    for (int i = 0; i < n; i++) {
        overlap = doesOverlap(intervals[i], newInterval);
        if (!overlap) {
            result.push_back(intervals[i]);

            // case 4
            if (i < n && newInterval[0] > intervals[i][1] && newInterval[1] < intervals[i + 1][0])
                result.push_back(newInterval);

            continue;
        }

        // case 5: Merge Overlapping intervals.
        vector<int> temp;
        temp[0] = min(newInterval[0], intervals[i][0]);

        // Traverse the set until intervals are overlapping
        while (i < n && overlap) {
            // ending time of the newly merged interval is the maximum ending time of both
            // overlapping intervals.
            temp[1] = max(newInterval[1], intervals[i][1]);

            if (i == n - 1)
                overlap = false;
            else
                overlap = doesOverlap(intervals[i + 1], newInterval);
            i++;
        }

        i--;
        result.push_back(temp);
    }

    return result;
}

bool doesOverlap(vector<int> a, vector<int> b) {
    return (min(a[1], b[1]) >= max(a[0], b[0]));
}

Временная сложность этого подхода составляет O(n), а пространственная сложность — O(n).

Подход 2: использование интервалов слияния

Как упоминалось выше, мы можем использовать подход Merge Intervals для решения этой проблемы.

Мы вставляем новый интервал в список и используем решение интервалов слияния.

Фрагмент C++ этого подхода выглядит следующим образом:

vector<vector<int>> merge(vector<vector<int>>& intervals, vector<int> newInterval) {
    intervals.push_back(newInterval);
    sort(intervals.begin(), intervals.end());

    vector<vector<int>> result;

    for(auto interval: intervals){
        if(result.empty() || (result.back()[1] < interval[0])){
            result.push_back({interval[0], interval[1]});
        } else {
            result.back()[1] = max(result.back()[1], interval[1]);
        }
    }

    return result;
}

Временная сложность этого подхода составляет O(n * log n), потому что мы сортируем список. Сложность пространства составляет O(1).

Подход 3: использование стека

Мы используем стек, чтобы определить интервал, в котором он может быть объединен или помещен в правильную позицию.

Фрагмент C++ этого подхода выглядит следующим образом:

vector<vector<int>> merge(vector<vector<int>>& intervals, vector<int> newInterval) {
    stack< pair<int, int> > st;

    // push the first interval to stack
    st.push(intervals[0]);

    // store the top element of the stack
    vector<int> top = st.top();

    // Checking is newInterval[0] is less than top[1]
    if (newInterval[0] < top[1]) {
        // pop the top element as it will merge with the
        // previous range
        st.pop();

        // re-assign top[0]
        top[0] = min(top[0], newInterval[0]);

        // re-assign top[1]
        top[1] = max(top[1], newInterval[1]);

        // push the current interval
        st.push(top);
    } else {
       st.push(newInterval);
    }

    // iterate from i = 1 to n - 1
    for (int i = 1; i < n; i++) {
        // store the top element of the stack st
        vector<int> top = st.top();

        // if intervals[i][0] is less than top[1]
        if (intervals[i][0] < top[1]) {
            st.pop();

            // re-assign top[0]
            top[0] = min(top[0], intervals[i][0]);

            // re-assign top[1]
            top[1] = max(top[1], intervals[i][1]);

            // push the current interval
            st.push(top);
        } else {
            st.push(intervals[i]);
        }
    }

    // storing the final intervals
    stack<vector<vector<int>>> result;

    // popping the stack elements
    while (st.empty() != true) {
        vector<int> element = st.top();
        st.pop();

        result.push(element);
    }

    return result;
}

Временная сложность этого подхода составляет O(n), а пространственная сложность — O(n).

Подход 4: Оптимизированное решение без использования дополнительного места

Мы можем решить эту проблему, не используя дополнительное пространство. В подходе 1 мы рассмотрели пять случаев. Нам нужно явно обработать только случаи 1 и 4, а остальные случаи можно обработать в одном цикле.

Сначала проверим алгоритм.

Алгоритм

// set size of intervals array
- n = intervals.size()
  i = 0

// iterate over the intervals list till the new interval start value is less than
// any of the interval's end values in the list
- loop while i < n && intervals[i][1] < newInterval[0]

  // keep adding the intervals to the final result
  - result.push_back(intervals[i])

  - increment i; i++
- end while

// once we find the correct slot, now loop till the new interval end value is greater than
// any of the interval's start values in the list
- loop while i < n && newInterval[1] >= intervals[i][0]

  // this code will handle the merging of the intervals based on
  // new interval start and end values
  // we also update the values of the new interval
  - newInterval[0] = min(newInterval[0], intervals[i][0])
  - newInterval[1] = max(newInterval[1], intervals[i][1])

  - increment i; i++
- end while

// append the new interval to result
- result.push_back(newInterval)

// append the remaining intervals of the list to the result
- loop while i < n
  - result.push_back(intervals[i])
  - increment i; i++
- end while

- return result

Временная сложность этого подхода составляет O(n), а пространственная сложность — O(1).

Ознакомьтесь с нашими решениями на C++, Golang и Javascript.

С++ решение

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        int n = intervals.size(), i = 0;
        vector<vector<int>> result;

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

        while(i < n && newInterval[1] >= intervals[i][0]){
            newInterval[0] = min(newInterval[0], intervals[i][0]);
            newInterval[1] = max(newInterval[1], intervals[i][1]);
            i++;
        }

        result.push_back(newInterval);

        while(i < n){
            result.push_back(intervals[i]);
            i++;
        }

        return result;
    }
};

Голанг решение

func insert(intervals [][]int, newInterval []int) [][]int {
    n, i := len(intervals), 0
    var result [][]int

    for i < n && intervals[i][1] < newInterval[0] {
        result = append(result, intervals[i])
        i++
    }

    for i < n && newInterval[1] >= intervals[i][0] {
        newInterval[0] = min(newInterval[0], intervals[i][0])
        newInterval[1] = max(newInterval[1], intervals[i][1])
        i++
    }

    result = append(result, newInterval)

    for i < n {
        result = append(result, intervals[i])
        i++
    }

    return result
}

func min(a, b int) int {
    if a < b {
        return a
    }

    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }

    return b
}

JavaScript-решение

/**
 * @param {number[][]} intervals
 * @param {number[]} newInterval
 * @return {number[][]}
 */
var insert = function(intervals, newInterval) {
    let n = intervals.length, i = 0;
    let result = [];

    while(i < n && intervals[i][1] < newInterval[0]){
        result.push(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++;
    }

    result.push(newInterval);

    while(i < n){
        result.push(intervals[i]);
        i++;
    }

    return result;
};

Пробный прогон

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

Input: intervals = [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]]
       newInterval = [4, 8]

Step 1: n = intervals.size()
          = 5
        i = 0
        vector<vector<int>> result

Step 2: loop while i < n && intervals[i][1] < newInterval[0]
          0 < 5 && intervals[0][1] < newInterval[0]
          true && 2 < 4
          true

          result.push_back(intervals[i])
          result.push_back(intervals[0])
          result.push_back([1, 2])
          result = [[1, 2]]

          i++
          i = 1

        loop while i < n && intervals[i][1] < newInterval[0]
          1 < 5 && intervals[1][1] < newInterval[0]
          true && 5 < 4
          false

Step 3: loop while i < n && newInterval[1] >= intervals[i][0]
          1 < 5 && newInterval[1] >= intervals[1][0]
          true && 8 >= 3
          true

          newInterval[0] = Math.min(newInterval[0], intervals[i][0])
                         = Math.min(newInterval[0], intervals[1][0])
                         = Math.min(4, 3)
                         = 3

          newInterval[1] = Math.max(newInterval[1], intervals[i][1])
                         = Math.max(newInterval[1], intervals[1][1])
                         = Math.max(8, 5)
                         = 8

          newInterval = [3, 8]

          i++
          i = 2

        loop while i < n && newInterval[1] >= intervals[i][0]
          2 < 5 && newInterval[1] >= intervals[2][0]
          true && 8 >= 6
          true

          newInterval[0] = Math.min(newInterval[0], intervals[i][0])
                         = Math.min(newInterval[0], intervals[1][0])
                         = Math.min(3, 6)
                         = 3

          newInterval[1] = Math.max(newInterval[1], intervals[i][1])
                         = Math.max(newInterval[1], intervals[1][1])
                         = Math.max(8, 7)
                         = 8

          newInterval = [3, 8]

          i++
          i = 3

        loop while i < n && newInterval[1] >= intervals[i][0]
          3 < 5 && newInterval[1] >= intervals[3][0]
          true && 8 >= 8
          true

          newInterval[0] = Math.min(newInterval[0], intervals[i][0])
                         = Math.min(newInterval[0], intervals[3][0])
                         = Math.min(3, 8)
                         = 3

          newInterval[1] = Math.max(newInterval[1], intervals[i][1])
                         = Math.max(newInterval[1], intervals[3][1])
                         = Math.max(8, 10)
                         = 10

          newInterval = [3, 10]

          i++
          i = 4

        loop while i < n && newInterval[1] >= intervals[i][0]
          4 < 5 && newInterval[1] >= intervals[4][0]
          true && 8 >= 12
          false

Step 4: result.push_back(newInterval)
        result.push_back([3, 10])
        result = [[1, 2], [3, 10]]

Step 5: loop while i < n
          4 < 5
          true

          result.push_back(intervals[i])
          result.push_back(intervals[4])
          result.push_back([12, 16])
          result = [[1, 2], [3, 10], [12, 16]]

          i++
          i = 5

        loop while i < n
          5 < 5
          false

Step 6: return result

We return the answer as [[1, 2], [3, 10], [12, 16]].

Первоначально опубликовано на https://alkeshghorpade.me.