專欄：50多種數據結構徹底征服

專欄：50多種經典圖論算法全部掌握

付費上班曾經是一句玩笑，沒想到現在卻變成了現實。最近一網友開了一家假裝上班公司，每天只需要30元，中午還提供一頓飯。

之前在網上也經常看到某某失業之后不敢讓家里人知道，白天就到公園里閑逛，假裝去上班，還有的是去星巴克，一坐就是一整天。其實我覺得這個真沒必要，失業又不是得了絕癥，和家里人溝通一下，還是能理解的，誰還沒經歷過失業？除了體制內的我估計至少80%的人都會經歷過失業，有的還會經歷過多次。失業沒什么，沒必要假裝去上班。

--------------下面是今天的算法題--------------

來看下今天的算法題，這題是LeetCode的第56題：合并區間。

問題描述

來源：LeetCode第56題

難度：中等

以數組 intervals 表示若干個區間的集合，其中單個區間為 intervals[i] = [starti, endi] 。請你合并所有重疊的區間，并返回 一個不重疊的區間數組，該數組需恰好覆蓋輸入中的所有區間 。

示例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] 可被視為重疊區間。

• 1 <= intervals.length <= 10^4

• intervals[i].length == 2

• 0 <= starti <= endi <= 10^4

問題分析

這題讓合并區間，并且合并之后的區間沒有重疊，實際上就是讓把重疊的區間給合并，怎么判斷區間有沒有重疊呢？我們以示例一為例畫個圖來看下。

如上圖所示，要判斷兩個區間有沒有重疊，我們 先對所有區間按照起始點進行排序 ，排序之后如果 后面區間的起始點小于前面區間的終止點 ，比如區間[2,6]和區間[1,3]，那么這兩個區間肯定有重疊，我們需要把他倆合并即可，合并之后的區間是[1,6]，然后這個區間還要繼續和后面的區間比較。

如果 后面區間的起始點大于前面區間的終止點 ，比如上面合并之后的區間[1,6]和區間[8，10]，那么這兩個區間肯定是沒有重疊的，我們需要把前面的區間[1,6]添加到集合中，后面的區間[8，10]先不要添加，因為后面還需要查找和[8，10]有沒有重疊的區間。

JAVA：

public int[][] merge(int[][] intervals) {     // 按照起始點對數組進行排序     Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));     int start = intervals[0][0];     int end = intervals[0][1];     List

  ans = new ArrayList<>();     for (int[] interval : intervals) {         if (interval[0] <= end) {// 當前區間和前面區間合并             end = Math.max(end, interval[1]);         } else {// 當前區間和前面區間不能合并，把前面的區間添加進來。             ans.add(new int[]{start, end});             start = interval[0];             end = interval[1];         }     }     ans.add(new int[]{start, end});// 最后的區間要單獨添加。     // 把集合轉為數組。     return ans.toArray(new int[ans.size()][]); }

C++：

public:     vector

 > merge(vector

 > &intervals) {         // 按照起始點對數組進行排序         sort(intervals.begin(), intervals.end());         int start = intervals[0][0];         int end = intervals[0][1];         vector

 > ans;         for (vector

  &interval: intervals) {             if (interval[0] <= end) {// 當前區間和前面區間合并                 end = max(end, interval[1]);             } else {// 當前區間和前面區間不能合并，把前面的區間添加進來。                 ans.push_back({start, end});                 start = interval[0];                 end = interval[1];             }         }         ans.push_back({start, end});// 最后的區間要單獨添加。         return ans;     }

Python：

def merge(self, intervals: List[List[int]]) -> List[List[int]]:     # 按照起始點對數組進行排序     intervals.sort(key=lambda x: x[0])     ans = []     start, end = intervals[0][0], intervals[0][1]     for interval in intervals:         if interval[0] <= end:  # 當前區間和前面區間合并             end = max(end, interval[1])         else:  # 當前區間和前面區間不能合并，把前面的區間添加進來。             ans.append([start, end])             start = interval[0]             end = interval[1]     ans.append([start, end])  # 最后的區間要單獨添加。     return ans

筆者簡介

博哥，真名：王一博，畢業十多年， 作者，專注于 數據結構和算法 的講解，在全球30多個算法網站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注，也可以 下載我整理的1000多頁的PDF算法文檔 。