:orphan:

Insert Interval
===============

.. highlight:: none

Problem
-------
https://leetcode.com/problems/insert-interval/

You are given an array of non-overlapping intervals ``intervals`` where
``intervals[i] = [start``\ :sub:`i`\ ``, end``\ :sub:`i`\ ``]``
represent the start and the end of the ``i``\ :sup:`th` interval and
``intervals`` is sorted in ascending order by ``start``\ :sub:`i`. You
are also given an interval ``newInterval = [start, end]`` that
represents the start and end of another interval.

Insert ``newInterval`` into ``intervals`` such that ``intervals`` is
still sorted in ascending order by ``start``\ :sub:`i` and
``intervals`` still does not have any overlapping intervals (merge
overlapping intervals if necessary).

Return ``intervals`` *after the insertion*.



**Example 1:**

::

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

**Example 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].



**Constraints:**

- ``0 <= intervals.length <= 10``\ :sup:`4`
- ``intervals[i].length == 2``
- ``0 <= start``\ :sub:`i`\ ``<= end``\ :sub:`i`\ ``<= 10``\ :sup:`5`
- ``intervals`` is sorted by ``start``\ :sub:`i` in **ascending** order.
- ``newInterval.length == 2``
- ``0 <= start <= end <= 10``\ :sup:`5`

.. highlight:: python

Pattern
-------
Array, Intervals

Approaches
----------

.. tab-set::

    .. tab-item:: Greedy

        **Code**

        .. literalinclude:: ../problems/medium/insert-interval/insert_interval__greedy.py
            :language: python
            :lines: 12-

        **Test**

        >>> from insert_interval__greedy import insert
        >>> insert([[1, 3], [6, 9]], [2, 5])
        [[1, 5], [6, 9]]
        >>> insert([[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], [4, 8])
        [[1, 2], [3, 10], [12, 16]]
        >>> insert([], [5, 7])
        [[5, 7]]

        .. autofunction:: insert_interval__greedy.insert

    .. tab-item:: Insert Then Merge

        **Code**

        .. literalinclude:: ../problems/medium/insert-interval/insert_interval__insert_then_merge.py
            :language: python
            :lines: 12-

        **Test**

        >>> from insert_interval__insert_then_merge import insert
        >>> insert([[1, 3], [6, 9]], [2, 5])
        [[1, 5], [6, 9]]
        >>> insert([[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], [4, 8])
        [[1, 2], [3, 10], [12, 16]]
        >>> insert([], [5, 7])
        [[5, 7]]

        .. autofunction:: insert_interval__insert_then_merge.insert