# 0056. 合并區間 ## 題目地址(56. 合并區間) <https://leetcode-cn.com/problems/merge-intervals/> ## 題目描述 ``` <pre class="calibre18">``` 給出一個區間的集合，請合并所有重疊的區間。 示例 1: 輸入: intervals = [[1,3],[2,6],[8,10],[15,18]] 輸出: [[1,6],[8,10],[15,18]] 解釋: 區間 [1,3] 和 [2,6] 重疊, 將它們合并為 [1,6]. 示例 2: 輸入: intervals = [[1,4],[4,5]] 輸出: [[1,5]] 解釋: 區間 [1,4] 和 [4,5] 可被視為重疊區間。 注意：輸入類型已于2019年4月15日更改。 請重置默認代碼定義以獲取新方法簽名。 提示： intervals[i][0] <= intervals[i][1] ``` ``` ## 前置知識 - 排序 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路 - 先對數組進行排序，排序的依據就是每一項的第一個元素的大小。 - 然后我們對數組進行遍歷，遍歷的時候兩兩運算（具體運算邏輯見下） - 判斷是否相交，如果不相交，則跳過 - 如果相交，則合并兩項 ## 關鍵點解析 - 對數組進行排序簡化操作 - 如果不排序，需要借助一些 hack,這里不介紹了 ## 代碼 - 語言支持: Javascript，Python3 ``` <pre class="calibre18">``` <span class="hljs-title">/* * @lc app=leetcode id=56 lang=javascript * * [56] Merge Intervals */</span> <span class="hljs-title">/** * @param {number[][]} intervals * @return {number[][]} */</span> <span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">intersected</span>(<span class="hljs-params">a, b</span>) </span>{ <span class="hljs-keyword">if</span> (a[<span class="hljs-params">0</span>] > b[<span class="hljs-params">1</span>] || a[<span class="hljs-params">1</span>] < b[<span class="hljs-params">0</span>]) <span class="hljs-keyword">return</span> <span class="hljs-params">false</span>; <span class="hljs-keyword">return</span> <span class="hljs-params">true</span>; } <span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">mergeTwo</span>(<span class="hljs-params">a, b</span>) </span>{ <span class="hljs-keyword">return</span> [<span class="hljs-params">Math</span>.min(a[<span class="hljs-params">0</span>], b[<span class="hljs-params">0</span>]), <span class="hljs-params">Math</span>.max(a[<span class="hljs-params">1</span>], b[<span class="hljs-params">1</span>])]; } <span class="hljs-keyword">var</span> merge = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">intervals</span>) </span>{ <span class="hljs-title">// 這種算法需要先排序</span> intervals.sort((a, b) => a[<span class="hljs-params">0</span>] - b[<span class="hljs-params">0</span>]); <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">0</span>; i < intervals.length - <span class="hljs-params">1</span>; i++) { <span class="hljs-keyword">const</span> cur = intervals[i]; <span class="hljs-keyword">const</span> next = intervals[i + <span class="hljs-params">1</span>]; <span class="hljs-keyword">if</span> (intersected(cur, next)) { intervals[i] = <span class="hljs-params">undefined</span>; intervals[i + <span class="hljs-params">1</span>] = mergeTwo(cur, next); } } <span class="hljs-keyword">return</span> intervals.filter((q) => q); }; ``` ``` Python3 Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">merge</span><span class="hljs-params">(self, intervals: List[List[int]])</span> -> List[List[int]]:</span> <span class="hljs-string">"""先排序，后合并"""</span> <span class="hljs-keyword">if</span> len(intervals) <= <span class="hljs-params">1</span>: <span class="hljs-keyword">return</span> intervals <span class="hljs-title"># 排序</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">get_first</span><span class="hljs-params">(a_list)</span>:</span> <span class="hljs-keyword">return</span> a_list[<span class="hljs-params">0</span>] intervals.sort(key=get_first) <span class="hljs-title"># 合并</span> res = [intervals[<span class="hljs-params">0</span>]] <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-params">1</span>, len(intervals)): <span class="hljs-keyword">if</span> intervals[i][<span class="hljs-params">0</span>] <= res[<span class="hljs-params">-1</span>][<span class="hljs-params">1</span>]: res[<span class="hljs-params">-1</span>] = [res[<span class="hljs-params">-1</span>][<span class="hljs-params">0</span>], max(res[<span class="hljs-params">-1</span>][<span class="hljs-params">1</span>], intervals[i][<span class="hljs-params">1</span>])] <span class="hljs-keyword">else</span>: res.append(intervals[i]) <span class="hljs-keyword">return</span> res ``` ``` ***復雜度分析*** - 時間復雜度：由于采用了排序，因此復雜度大概為 O(NlogN)O(NlogN)O(NlogN) - 空間復雜度：O(N)O(N)O(N)