秒懂力扣區(qū)間題目：重疊區(qū)間、合并區(qū)間、插入?yún)^(qū)間

今天的力扣打卡題是 57. 插入?yún)^(qū)間 ，我們再順便練習(xí)兩道類似的簡單區(qū)間題目，比如：判斷區(qū)間是否重疊（252. 會議室）、56. 合并區(qū)間。這類面試題目還挺討巧的，因為不需要掌握什么數(shù)據(jù)結(jié)構(gòu)與算法的先驗知識，看懂題目之后模擬一遍即可，很容易考察出應(yīng)聘者到底會不會寫代碼。

一、判斷區(qū)間是否重疊

題目描述

力扣 252. 會議室
難度：Easy

給定一個會議時間安排的數(shù)組 intervals ，每個會議時間都會包括開始和結(jié)束的時間 intervals[i] = [starti, endi] ，請你判斷一個人是否能夠參加這里面的全部會議。

示例 1:：
輸入: intervals = [[0,30],[5,10],[15,20]]
輸出: false
解釋: 存在重疊區(qū)間，一個人在同一時刻只能參加一個會議。

示例 2:：
輸入: intervals = [[7,10],[2,4]]
輸出: true
解釋: 不存在重疊區(qū)間。

思路分析

因為一個人在同一時刻只能參加一個會議，因此題目實質(zhì)是判斷是否存在重疊區(qū)間，這個簡單，將區(qū)間按照會議開始時間進行排序，然后遍歷一遍判斷即可。

代碼實現(xiàn)

class?Solution?{
????public?boolean?canAttendMeetings(int[][]?intervals)?{
????????//?將區(qū)間按照會議開始實現(xiàn)升序排序
????????Arrays.sort(intervals,?(v1,?v2)?->?v1[0]?-?v2[0]);
????????//?遍歷會議，如果下一個會議在前一個會議結(jié)束之前就開始了，返回 false。
????????for?(int?i?=?1;?i?????????????if?(intervals[i][0]?1][1])?{
????????????????return?false;
????????????}
????????}
????????return?true;
????}
}

二、合并區(qū)間

題目描述

力扣 56. 合并區(qū)間
難度：Medium

給出一個區(qū)間的集合，請合并所有重疊的區(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ū)間。

思路分析

和上一題一樣，首先對區(qū)間按照起始端點進行升序排序，然后逐個判斷當(dāng)前區(qū)間是否與前一個區(qū)間重疊，如果不重疊的話將當(dāng)前區(qū)間直接加入結(jié)果集，反之如果重疊的話，就將當(dāng)前區(qū)間與前一個區(qū)間進行合并。

代碼實現(xiàn)

class?Solution?{
????public?int[][]?merge(int[][]?intervals)?{
????????//?先按照區(qū)間起始位置排序
????????Arrays.sort(intervals,?(v1,?v2)?->?v1[0]?-?v2[0]);
????????//?遍歷區(qū)間
????????int[][]?res?=?new?int[intervals.length][2];
????????int?idx?=?-1;
????????for?(int[]?interval:?intervals)?{
????????????//?如果結(jié)果數(shù)組是空的，或者當(dāng)前區(qū)間的起始位置?>?結(jié)果數(shù)組中最后區(qū)間的終止位置，說明不重疊。
????????????//?則不合并，直接將當(dāng)前區(qū)間加入結(jié)果數(shù)組。
????????????if?(idx?==?-1?||?interval[0]?>?res[idx][1])?{
????????????????res[++idx]?=?interval;
????????????}?else?{
????????????????//?反之說明重疊，則將當(dāng)前區(qū)間合并至結(jié)果數(shù)組的最后區(qū)間
????????????????res[idx][1]?=?Math.max(res[idx][1],?interval[1]);
????????????}
????????}
????????return?Arrays.copyOf(res,?idx?+?1);
????}
}

三、插入?yún)^(qū)間

題目描述

57. 插入?yún)^(qū)間
難度：Medium

給出一個無重疊的 ，按照區(qū)間起始端點排序的區(qū)間列表。

在列表中插入一個新的區(qū)間，你需要確保列表中的區(qū)間仍然 有序且不重疊（如果有必要的話，可以 合并區(qū)間）。

示例 1:：
輸入: intervals = [[1,3],[6,9]], newInterval = [2,5]
輸出: [[1,5],[6,9]]
解釋: 新區(qū)間[2,5] 與 [1,3]重疊，因此合并成為 [1,5]。

示例 2:：
輸入: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
輸出: [[1,2],[3,10],[12,16]]
解釋: 新區(qū)間 [4,8] 與 [3,5],[6,7],[8,10] 重疊，因此合并成為 [3,10]。

思路分析

本題中的區(qū)間已經(jīng)按照起始端點升序排列，因此我們直接遍歷區(qū)間列表，尋找新區(qū)間的插入位置即可。具體步驟如下：

1. 首先將新區(qū)間左邊且相離的區(qū)間加入結(jié)果集（遍歷時，如果當(dāng)前區(qū)間的結(jié)束位置小于新區(qū)間的開始位置，說明當(dāng)前區(qū)間在新區(qū)間的左邊且相離）；

2. 接著判斷當(dāng)前區(qū)間是否與新區(qū)間重疊，重疊的話就進行合并，直到遍歷到當(dāng)前區(qū)間在新區(qū)間的右邊且相離，將最終合并后的新區(qū)間加入結(jié)果集；

3. 最后將新區(qū)間右邊且相離的區(qū)間加入結(jié)果集。

代碼實現(xiàn)

class?Solution?{
????public?int[][]?insert(int[][]?intervals,?int[]?newInterval)?{
????????int[][]?res?=?new?int[intervals.length?+?1][2];
????????int?idx?=?0;
????????//?遍歷區(qū)間列表：
????????//?首先將新區(qū)間左邊且相離的區(qū)間加入結(jié)果集
????????int?i?=?0;
????????while?(i?1]?0])?{
????????????res[idx++]?=?intervals[i++];
????????}
????????//?接著判斷當(dāng)前區(qū)間是否與新區(qū)間重疊，重疊的話就進行合并，直到遍歷到當(dāng)前區(qū)間在新區(qū)間的右邊且相離，
????????//?將最終合并后的新區(qū)間加入結(jié)果集
????????while?(i?0]?<=?newInterval[1])?{
????????????newInterval[0]?=?Math.min(intervals[i][0],?newInterval[0]);
????????????newInterval[1]?=?Math.max(intervals[i][1],?newInterval[1]);
????????????i++;
????????}
????????res[idx++]?=?newInterval;
????????//?最后將新區(qū)間右邊且相離的區(qū)間加入結(jié)果集
????????while?(i?????????????res[idx++]?=?intervals[i++];
????????}

????????return?Arrays.copyOf(res,?idx);
????}
}

四、題目拓展

力扣1288. 刪除被覆蓋區(qū)間
難度：Easy

給你一個區(qū)間列表，請你刪除列表中被其他區(qū)間所覆蓋的區(qū)間。在完成所有刪除操作后，請你返回列表中剩余區(qū)間的數(shù)目。（對于區(qū)間 [a,b) 和區(qū)間 [c,d)，若 c <= a 且 d >= b ，則區(qū)間 [a,b) 被區(qū)間 [c,d) 覆蓋）

示例：
輸入：intervals = [[1,4],[3,6],[2,8]]
輸出：2
解釋：區(qū)間 [3,6] 被區(qū)間 [2,8] 覆蓋，所以它被刪除了。

思路分析：本題和本文第一題的做法一樣～首先按照區(qū)間起始端點進行排序，然后遍歷區(qū)間，將第一題的判斷區(qū)間是否重疊改為判斷區(qū)間是否覆蓋即可。

力扣228. 匯總區(qū)間
難度：Medium

給定一個無重復(fù)元素的有序整數(shù)數(shù)組 nums，返回 恰好覆蓋數(shù)組中所有數(shù)字 的 最小有序 區(qū)間范圍列表。也就是說 nums 的每個元素都恰好被某個區(qū)間范圍所覆蓋，并且不存在屬于某個范圍但不屬于 nums 的數(shù)字。

示例：
輸入：nums = [0,1,2,4,5,7]
輸出：["0->2","4->5","7"]

思路分析：本題是在有序數(shù)組中，找出連續(xù)遞增的區(qū)間，是雙指針/滑動窗口的經(jīng)典題目，和本文中的其他區(qū)間題目不是一種類型，我們在之后的文章中再介紹雙指針和滑動窗口的模板哈～

力扣354. 俄羅斯套娃信封問題
難度：Hard

給定一些標記了寬度和高度的信封，寬度和高度以整數(shù)對形式?(w, h)?出現(xiàn)。當(dāng)另一個信封的寬度和高度都比這個信封大的時候，這個信封就可以放進另一個信封里，如同俄羅斯套娃一樣。

請計算最多能有多少個信封能組成一組“俄羅斯套娃”信封（即可以把一個信封放到另一個信封里面）。

示例：
輸入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
解釋：最多信封的個數(shù)為 3, 組合為: [2,3] => [5,4] => [6,7]。

思路分析：本題實質(zhì)是求最長嵌套區(qū)間的長度，是經(jīng)典題目「最長上升子序列」的變種，解法也一模一樣，有動態(tài)規(guī)劃 和 二分 兩種經(jīng)典解法。由于本題和本文中的其他區(qū)間題目不是一種類型，所以我們在后續(xù)的章節(jié)里再「秒懂最長上升子序列問題及其系列變種」吧！