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

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

2025年 1 月 15 日馬斯克在X(以前的推特)上發(fā)文稱：他們招聘軟件工程師不關(guān)心你的學(xué)歷，或者你是否上過大學(xué)以及是否在哪個大廠工作過，只需要展示你的代碼即可。不過我感覺這不是很靠譜，因為讀代碼要比看簡歷難多了，發(fā)給你一份代碼要看到啥時候，并且看代碼還需要專業(yè)的人才能看，hr不一定看的懂，現(xiàn)在很多hr連簡歷都看不過來，直接使用篩選功能。不過這也給那些學(xué)歷不高但能力很強(qiáng)的人更多的機(jī)會。

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

來看下今天的算法題，這題是LeetCode的第57題：插入?yún)^(qū)間。

問題描述

來源：LeetCode第57題

難度：中等

給你一個無重疊的，按照區(qū)間起始端點排序的區(qū)間列表 intervals，其中 intervals[i] = [starti, endi] 表示第 i 個區(qū)間的開始和結(jié)束，并且 intervals 按照 starti 升序排列。同樣給定一個區(qū)間 newInterval = [start, end] 表示另一個區(qū)間的開始和結(jié)束。

在 intervals 中插入?yún)^(qū)間 newInterval，使得 intervals 依然按照 starti 升序排列，且區(qū)間之間不重疊（如果有必要的話，可以合并區(qū)間）。返回插入之后的 intervals。

示例1：

輸入：intervals = [[1,3],[6,9]], newInterval = [2,5] 輸出：[[1,5],[6,9]]

示例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] 重疊。

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

• intervals[i].length == 2

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

• intervals 根據(jù) starti 按 升序 排列

• newInterval.length == 2

• 0 <= start <= end <= 10^5

問題分析

這題說的是原來的區(qū)間是按照起始點排序的，且區(qū)間沒有重疊。讓我們在原來的區(qū)間插入一個新的區(qū)間，如果有重疊就把他們合并，如下圖所示，因為區(qū)間[1,3]和區(qū)間[2,5]有重疊，

這里要判斷要合并的區(qū)間和上面的哪些區(qū)間有重疊，因為上面的區(qū)間都已經(jīng)按照起始點排序了，如果 當(dāng)前區(qū)間的終點小于合并區(qū)間的起始點， 他們是沒有重疊的 ，或者 當(dāng)前區(qū)間的起始點大于合并區(qū)間的終點 ，他們也是沒有重疊的。

沒有重疊的區(qū)間只需要單獨保存下來，有重疊的區(qū)間需要合并。

JAVA：

public int[][] insert(int[][] intervals, int[] newInterval) {     List

  ans = new ArrayList<>();     for (int[] interval : intervals) {         if (newInterval == null || interval[1] < newInterval[0]) {             // 前面單獨的添加進(jìn)來，或者已經(jīng)合并完了，把后面的添加進(jìn)來             ans.add(interval);         } else if (interval[0] > newInterval[1]) {             ans.add(newInterval);// 后面單獨的區(qū)間。             ans.add(interval);             newInterval = null;         } else {// 合并區(qū)間             newInterval[0] = Math.min(newInterval[0], interval[0]);             newInterval[1] = Math.max(newInterval[1], interval[1]);         }     }     // 如果合并之后的區(qū)間沒有保存下來，要保存下來     if (newInterval != null)         ans.add(newInterval);     return ans.toArray(new int[ans.size()][]); }

C++：

public:     vector

 > insert(vector

 > &intervals, vector

  &newInterval) {         vector

 > res;         bool finish = false;// 合并完了，后面的不需要再合并了，直接添加         for (auto const &interval: intervals) {             if (finish || interval[1] < newInterval[0]) {                 res.emplace_back(interval);// 前面單獨             } else if (interval[0] > newInterval[1]) {// 后面單獨                 res.emplace_back(newInterval);                 res.emplace_back(interval);                 finish = true;             } else {// 有交叉，合并                 newInterval[0] = min(newInterval[0], interval[0]);//get min                 newInterval[1] = max(newInterval[1], interval[1]);//get max             }         }         if (!finish)             res.emplace_back(newInterval);         return res;     }

Python：

def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:     ans = []     for interval in intervals:         if not newInterval or interval[1] < newInterval[0]:             # 前面單獨的添加進(jìn)來，或者已經(jīng)合并完了，把后面的添加進(jìn)來             ans.append(interval)         elif interval[0] > newInterval[1]:             ans.append(newInterval[:])  # 后面單獨的區(qū)間。             ans.append(interval)             newInterval.clear()         else:  # 合并區(qū)間             newInterval[0] = min(newInterval[0], interval[0])             newInterval[1] = max(newInterval[1], interval[1])     # 如果合并之后的區(qū)間沒有保存下來，要保存下來     if newInterval:         ans.append(newInterval)     return ans

筆者簡介

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