:orphan:

Merge Intervals
===============

.. highlight:: none

Problem
-------
https://leetcode.com/problems/merge-intervals/

Given an array of ``intervals`` where
``intervals[i] = [start``\ :sub:```i```\ ``, end``\ :sub:```i```\ ``]``,
merge all overlapping intervals, and return *an array of the
non-overlapping intervals that cover all the intervals in the input*.

 

**Example 1:**

::


   Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
   Output: [[1,6],[8,10],[15,18]]
   Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

**Example 2:**

::


   Input: intervals = [[1,4],[4,5]]
   Output: [[1,5]]
   Explanation: Intervals [1,4] and [4,5] are considered overlapping.

**Example 3:**

::


   Input: intervals = [[4,7],[1,4]]
   Output: [[1,7]]
   Explanation: Intervals [1,4] and [4,7] are considered overlapping.

 

**Constraints:**

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

.. highlight:: python

Pattern
-------
Array, Sorting

Solution
--------
The key step is to sort ``intervals`` by their start point. We start merging
intervals from left to right. Add the first interval to ``merged_intervals``.
Suppose we have 2 sorted intervals :math:`[a, b]` in ``merged_intervals`` and
and :math:`[c, d]` in ``intervals``. We only need to check that :math:`c > b`
to merge the intervals to obtain :math:`[a, \\max(b, d)]`. Moreover, we only need to check
the next interval in ``intervals`` against the rightmost merged interval. This
is because the merged intervals are all disjoint and sorted from left to right.

Code
----

.. literalinclude:: ../problems/medium/merge-intervals/merge_intervals__approach_1.py
    :language: python
    :lines: 9-

Test
----
>>> from merge_intervals__approach_1 import merge
>>> merge([[1, 3], [2, 6], [8, 10], [15, 18]])
[[1, 6], [8, 10], [15, 18]]
>>> merge([[1, 4], [4, 5]])
[[1, 5]]

Complexity
----------
| :math:`n` is the number of intervals
| Time: :math:`O(n \log n)` — sort then merge intervals
| Auxiliary Space: :math:`O(1)`

.. autofunction:: merge_intervals__approach_1.merge