57. Insert Interval

LeetCode medium original: C# #array #csharp #intervals #leetcode #math #medium #sort
El texto de la tarea se traduce del ruso para el idioma seleccionado. El código no cambia.
LeetCode Static

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

intervals

, где

intervals[i] = [starti, endi]

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

intervals

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

starti

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

newInterval = [start, end]

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

Вставьте

newInterval

в arreglo

intervals

так, чтобы

intervals

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

starti

и в

intervals

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

return arreglo

intervals

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

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

intervals

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

Ejemplo

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

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

C# solución

coincidente/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++ solución

borrador automático, revisar antes de enviar 
#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 solución

coincidente/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 solución

coincidente/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 solución

coincidente/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 solución

coincidente/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 для хранения размера arregloа интервалов и текущего индекса соответственно, а также пустой arreglo res для хранения результата.

2️⃣

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

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

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

3️⃣

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

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

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

😎

Vacantes para esta tarea

Se muestran vacantes activas con etiquetas coincidentes.

Todas las vacantes
Todavía no hay vacantes activas.