專欄：50多種數(shù)據(jù)結(jié)構(gòu)徹底征服

專欄：50多種經(jīng)典圖論算法全部掌握

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

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

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

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

問題描述

來源：LeetCode第56題

難度：中等

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

示例1：

輸入：intervals = [[1,3],[2,6],[8,10],[15,18]] 輸出：[[1,6],[8,10],[15,18]] 解釋：區(qū)間 [1,3] 和 [2,6] 重疊, 將它們合并為 [1,6].

示例2：

輸入：intervals = [[1,4],[4,5]] 輸出：[[1,5]] 解釋：區(qū)間 [1,4] 和 [4,5] 可被視為重疊區(qū)間。

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

• intervals[i].length == 2

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

問題分析

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

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

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

JAVA：

public int[][] merge(int[][] intervals) {     // 按照起始點對數(shù)組進(jìn)行排序     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) {// 當(dāng)前區(qū)間和前面區(qū)間合并             end = Math.max(end, interval[1]);         } else {// 當(dāng)前區(qū)間和前面區(qū)間不能合并，把前面的區(qū)間添加進(jìn)來。             ans.add(new int[]{start, end});             start = interval[0];             end = interval[1];         }     }     ans.add(new int[]{start, end});// 最后的區(qū)間要單獨添加。     // 把集合轉(zhuǎn)為數(shù)組。     return ans.toArray(new int[ans.size()][]); }

C++：

public:     vector

 > merge(vector

 > &intervals) {         // 按照起始點對數(shù)組進(jìn)行排序         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) {// 當(dāng)前區(qū)間和前面區(qū)間合并                 end = max(end, interval[1]);             } else {// 當(dāng)前區(qū)間和前面區(qū)間不能合并，把前面的區(qū)間添加進(jìn)來。                 ans.push_back({start, end});                 start = interval[0];                 end = interval[1];             }         }         ans.push_back({start, end});// 最后的區(qū)間要單獨添加。         return ans;     }

Python：

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

筆者簡介

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