57. Insert interval

#include <stdlib.h>

static int *copyInterval(int start, int end) {
  int *p = malloc(2 * sizeof(int));
  p[0] = start;
  p[1] = end;
  return p;
}

int **insert(int **intervals, int intervalsSize, int *intervalsColSize,
             int *newInterval, int newIntervalSize, int *returnSize,
             int **returnColumnSizes) {
  (void)intervalsColSize;
  (void)newIntervalSize;
  int **result = malloc((intervalsSize + 1) * sizeof(int *));
  int n = 0, i = 0;
  int start = newInterval[0], end = newInterval[1];

  // 1. Intervals entirely before newInterval
  while (i < intervalsSize && intervals[i][1] < start) {
    result[n++] = copyInterval(intervals[i][0], intervals[i][1]);
    i++;
  }

  // 2. Intervals overlapping newInterval: absorb them into it
  while (i < intervalsSize && intervals[i][0] <= end) {
    if (intervals[i][0] < start)
      start = intervals[i][0];
    if (intervals[i][1] > end)
      end = intervals[i][1];
    i++;
  }
  result[n++] = copyInterval(start, end);

  // 3. Intervals entirely after newInterval
  while (i < intervalsSize) {
    result[n++] = copyInterval(intervals[i][0], intervals[i][1]);
    i++;
  }

  *returnSize = n;
  *returnColumnSizes = malloc(n * sizeof(int));
  for (int j = 0; j < n; j++)
    (*returnColumnSizes)[j] = 2;
  return result;
}

#include <algorithm>
#include <vector>

using namespace std;

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

    // 1. Intervals entirely before newInterval
    while (i < n && intervals[i][1] < newInterval[0])
      result.push_back(intervals[i++]);

    // 2. Intervals overlapping newInterval: absorb them into it
    while (i < n && intervals[i][0] <= newInterval[1]) {
      newInterval[0] = min(newInterval[0], intervals[i][0]);
      newInterval[1] = max(newInterval[1], intervals[i][1]);
      i++;
    }
    result.push_back(newInterval);

    // 3. Intervals entirely after newInterval
    while (i < n)
      result.push_back(intervals[i++]);

    return result;
  }
};

package intervals

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

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

    // 2. Intervals overlapping newInterval: absorb them into it
    for i < n && intervals[i][0] <= newInterval[1] {
        newInterval[0] = min(newInterval[0], intervals[i][0])
        newInterval[1] = max(newInterval[1], intervals[i][1])
        i++
    }
    result = append(result, newInterval)

    // 3. Intervals entirely after newInterval
    return append(result, intervals[i:]...)
}

import java.util.ArrayList;
import java.util.List;

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

        // 1. Intervals entirely before newInterval
        while (i < n && intervals[i][1] < newInterval[0])
            result.add(intervals[i++]);

        // 2. Intervals overlapping newInterval: absorb them into it
        while (i < n && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
            newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
            i++;
        }
        result.add(newInterval);

        // 3. Intervals entirely after newInterval
        while (i < n)
            result.add(intervals[i++]);

        return result.toArray(new int[0][]);
    }
}

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

  // 1. Intervals entirely before newInterval
  while (i < n && intervals[i][1] < newInterval[0]) result.push(intervals[i++]);

  // 2. Intervals overlapping newInterval: absorb them into it
  while (i < n && intervals[i][0] <= newInterval[1]) {
    newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
    newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
    i++;
  }
  result.push(newInterval);

  // 3. Intervals entirely after newInterval
  while (i < n) result.push(intervals[i++]);

  return result;
};

from typing import List


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

        # 1. Intervals entirely before newInterval
        while i < n and intervals[i][1] < newInterval[0]:
            result.append(intervals[i])
            i += 1

        # 2. Intervals overlapping newInterval: absorb them into it
        while i < n and intervals[i][0] <= newInterval[1]:
            newInterval[0] = min(newInterval[0], intervals[i][0])
            newInterval[1] = max(newInterval[1], intervals[i][1])
            i += 1
        result.append(newInterval)

        # 3. Intervals entirely after newInterval
        result.extend(intervals[i:])
        return result

impl Solution {
    pub fn insert(intervals: Vec<Vec<i32>>, mut new_interval: Vec<i32>) -> Vec<Vec<i32>> {
        let mut result = Vec::with_capacity(intervals.len() + 1);
        let mut i = 0;
        let n = intervals.len();

        // 1. Intervals entirely before new_interval
        while i < n && intervals[i][1] < new_interval[0] {
            result.push(intervals[i].clone());
            i += 1;
        }

        // 2. Intervals overlapping new_interval: absorb them into it
        while i < n && intervals[i][0] <= new_interval[1] {
            new_interval[0] = new_interval[0].min(intervals[i][0]);
            new_interval[1] = new_interval[1].max(intervals[i][1]);
            i += 1;
        }
        result.push(new_interval);

        // 3. Intervals entirely after new_interval
        result.extend_from_slice(&intervals[i..]);
        result
    }
}