:orphan:

Non-overlapping Intervals
=========================

.. highlight:: none

Problem
-------
https://leetcode.com/problems/non-overlapping-intervals/

Given an array of intervals ``intervals`` where ``intervals[i] =
[start``\ :sub:`i`\ ``, end``\ :sub:`i`\ ``]``, return *the minimum
number of intervals you need to remove to make the rest of the
intervals non-overlapping*.



**Example 1:**

::

   Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
   Output: 1
   Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.

**Example 2:**

::

   Input: intervals = [[1,2],[1,2],[1,2]]
   Output: 2
   Explanation: You need to remove two [1,2] to make the rest of the intervals non-overlapping.

**Example 3:**

::

   Input: intervals = [[1,2],[2,3]]
   Output: 0
   Explanation: You don't need to remove any of the intervals since they're already non-overlapping.



**Constraints:**

- ``1 <= intervals.length <= 10``\ :sup:`5`
- ``intervals[i].length == 2``
- ``-5 * 10``\ :sup:`4`\ ``<= start``\ :sub:`i`\ ``< end``\ :sub:`i`\ ``<= 5 * 10``\ :sup:`4`

.. highlight:: python

Pattern
-------
Array, Greedy, Intervals, Sorting

Approaches
----------

.. tab-set::

    .. tab-item:: Greedy

        **Code**

        .. literalinclude:: ../problems/medium/non-overlapping-intervals/non_overlapping_intervals__greedy.py
            :language: python
            :lines: 12-

        **Test**

        >>> from non_overlapping_intervals__greedy import eraseOverlapIntervals
        >>> eraseOverlapIntervals([[1, 2], [2, 3], [3, 4], [1, 3]])
        1
        >>> eraseOverlapIntervals([[1, 2], [1, 2], [1, 2]])
        2
        >>> eraseOverlapIntervals([[1, 2], [2, 3]])
        0

        .. autofunction:: non_overlapping_intervals__greedy.eraseOverlapIntervals