###### tags: `Leetcode` `medium` `array` `python` `Top 100 Liked Questions`

# 56. Merge Intervals

## [題目連結:]https://leetcode.com/problems/merge-intervals/

## 題目:
Given an array of ```intervals``` where ```intervals[i] = [starti, endi]```, 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.

## 解題想法:
兄弟題目: [57. Insert Interval](/eIk25ccNTuOVstZYvP122Q)
* 題目要求合併間格
* 先將每個間格[start,end]按照start排序
* 比較res[-1]的end與當前間格的start
* 若 res[-1]的end比較大
* 代表當前間格可以與其合併
* 則選res[-1]的end或是當前間格的end作為res[-1]新的end
* 否則表示當前間格並未與res重疊，加入res

* 示意圖:

    1~~~3 
      2~~~6
             8~~10
                    15~~18
res=  [1,6]  [8,10] [15,18]

## Python:

class Solution(object):
    def merge(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: List[List[int]]
        """
        #按照間個中第一個數字由小到大排序
        nums=sorted(intervals,key=lambda x:x[0])
        res=[nums[0]]
        for i in range(1,len(nums)):
            #res的尾vs當前的頭
            if res[-1][1]>=nums[i][0]:
                res[-1][1]=max(res[-1][1],nums[i][1])
            else:
                res.append(nums[i])
        return res

if __name__ == '__main__':
    result = Solution()
    intervals = [[1,3],[2,6],[8,10],[15,18]]
    ans = result.merge(intervals)
    print(ans)