57. Insert Interval

LeetCode medium original: C# #array #csharp #intervals #leetcode #math #medium #sort
Le texte du problème est traduit du russe pour la langue sélectionnée. Le code reste inchangé.
LeetCode Static

Вам дан tableau непересекающихся интервалов

intervals

, где

intervals[i] = [starti, endi]

представляет начало и конец i-го интервала, и tableau

intervals

отсортирован в порядке возрастания по

starti

. Вам также дан интервал

newInterval = [start, end]

, представляющий начало и конец другого интервала.

Вставьте

newInterval

в tableau

intervals

так, чтобы

intervals

оставался отсортированным в порядке возрастания по

starti

и в

intervals

не было бы перекрывающихся интервалов (при необходимости объедините перекрывающиеся интервалы).

return tableau

intervals

после вставки.

Обратите внимание, что не обязательно модифицировать tableau

intervals

на месте. Вы можете создать новый tableau и вернуть его.

Exemple

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

Output: [[1,5],[6,9]]

C# solution

correspondant/original 
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();
    }
}

C++ solution

brouillon automatique, à relire avant soumission 
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int[][] Insert(int[][] intervals, vector<int>& newInterval) {
        int n = intervals.size(), i = 0;
        List<int[]> res = new List<int[]>();
        while (i < n && intervals[i][1] < newInterval[0]) {
            res.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++;
        }
        res.push_back(newInterval);
        while (i < n) {
            res.push_back(intervals[i]);
            i++;
        }
        return res.ToArray();
    }
}

Java solution

correspondant/original 
class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int n = intervals.length, i = 0;
        List<int[]> res = new ArrayList<>();

        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(new int[res.size()][]);
    }
}

JavaScript solution

correspondant/original 
var insert = function (intervals, newInterval) {
    let n = intervals.length,
        i = 0,
        res = [];

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

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

    return res;
};

Python solution

correspondant/original 
class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        n = len(intervals)
        i = 0
        res = []

        while i < n and intervals[i][1] < newInterval[0]:
            res.append(intervals[i])
            i += 1

        while i < n and newInterval[1] >= intervals[i][0]:
            newInterval[0] = min(newInterval[0], intervals[i][0])
            newInterval[1] = max(newInterval[1], intervals[i][1])
            i += 1
        res.append(newInterval)

        while i < n:
            res.append(intervals[i])
            i += 1

        return res

Go solution

correspondant/original 
func insert(intervals [][]int, newInterval []int) [][]int {
    n := len(intervals)
    i := 0
    res := make([][]int, 0)

    for i < n && intervals[i][1] < newInterval[0] {
        res = append(res, 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++
    }
    res = append(res, newInterval)

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

    return res
}

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

Algorithm

1️⃣

Инициализация переменных:

Инициализируются переменные n и i для хранения размера tableauа интервалов и текущего индекса соответственно, а также пустой tableau res для хранения результата.

2️⃣

Обработка случаев без перекрытия и с перекрытием:

В случае отсутствия перекрытия до вставки, проходим через tableau интервалов до тех пор, пока конечная точка текущего интервала меньше начальной точки нового интервала. Добавляем текущий интервал в tableau res и переходим к следующему.

В случае перекрытия, продолжаем обход, пока начальная точка нового интервала меньше или равна конечной точке текущего интервала. Обновляем начальные и конечные точки нового интервала, объединяя перекрывающиеся интервалы в один.

3️⃣

Обработка интервалов после вставки:

Проходим через оставшиеся интервалы после индекса i и добавляем их в tableau res. Это включает интервалы, которые следуют после нового интервала и не перекрываются с ним.

Возвращаем tableau res, содержащий все интервалы с корректно вставленным новым интервалом.

😎

Vacancies for this task

offres actives with overlapping task tags are affichés.

Toutes les offres
Il n'y a pas encore d'offres actives.