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

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

最近一份針對(duì)字節(jié)跳動(dòng)豆包大模型負(fù)責(zé)人喬木的舉報(bào)文件在網(wǎng)上流傳，內(nèi)容是喬木婚內(nèi)出軌同組HRBP程某，且存在經(jīng)濟(jì)問(wèn)題（公款攜程某某赴美出差、拒付女兒撫養(yǎng)費(fèi)等）。

3月28日據(jù)多名內(nèi)部人士透露，喬木和程某的飛書(shū)賬號(hào)狀態(tài)顯示暫停使用，有內(nèi)部人士表示這意味著公司內(nèi)部或已啟動(dòng)調(diào)查。

喬木畢業(yè)于西安交大，2014年加入字節(jié)跳動(dòng)，他的妻子羅某某也是西安交大的本科生，中山大學(xué)碩士，有兩個(gè)女兒一個(gè)3歲，一個(gè)8歲。網(wǎng)上的傳言比較多，下面是我用豆包的提問(wèn)，已經(jīng)簡(jiǎn)要概述了。

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

來(lái)看下今天的算法題，這題是LeetCode的第1288題：刪除被覆蓋區(qū)間，難度是中等。

給你一個(gè)區(qū)間列表，請(qǐng)你刪除列表中被其他區(qū)間所覆蓋的區(qū)間。只有當(dāng) c <= a 且 b <= d 時(shí)，我們才認(rèn)為區(qū)間 [a,b) 被區(qū)間 [c,d) 覆蓋。

在完成所有刪除操作后，請(qǐng)你返回列表中剩余區(qū)間的數(shù)目。

示例1：

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

• 1 <= intervals.length <= 1000

• 0 <= intervals[i][0] < intervals[i][1] <= 10^5

• 對(duì)于所有的 i != j：intervals[i] != intervals[j]

問(wèn)題分析

這題說(shuō)的是刪除重疊區(qū)間后，返回剩余區(qū)間的數(shù)量，所謂重疊區(qū)間，就是一個(gè)區(qū)間完全被另一個(gè)區(qū)間給覆蓋了。

我們先對(duì)所有區(qū)間按照起始點(diǎn)從小到大排序，如果起始點(diǎn)相同，則按照區(qū)間終點(diǎn)從大到小排序。排序之后，下一個(gè)區(qū)間的起始點(diǎn)一定不下于前一個(gè)區(qū)間的起始點(diǎn)，我們只需要判斷下一個(gè)區(qū)間的終點(diǎn)是否小于前一個(gè)區(qū)間的終點(diǎn)end即可。

如果下一個(gè)區(qū)間的終點(diǎn)小于等于前一個(gè)區(qū)間的終點(diǎn)end，說(shuō)明下一個(gè)區(qū)間被前一個(gè)區(qū)間給覆蓋了，要累加覆蓋區(qū)間的個(gè)數(shù)。如果下一個(gè)區(qū)間的終點(diǎn)大于前一個(gè)區(qū)間的終點(diǎn)end，說(shuō)明下個(gè)區(qū)間沒(méi)有覆蓋，要更新end的值。

最后用總的區(qū)間數(shù)量減去覆蓋的區(qū)間數(shù)量，就是剩余區(qū)間的數(shù)量。

JAVA：

public int removeCoveredIntervals(int[][] intervals) {     // 根據(jù)起始位置，從小到大排序，如果起始位置大小一樣，就根據(jù)指針位置按照從大到小排序。     Arrays.sort(intervals, (o1, o2) -> {         if (o1[0] == o2[0])             return o2[1] - o1[1];         return o1[0] - o2[0];     });     int end = intervals[0][1];     int cnt = 0;// 刪除的區(qū)間數(shù)量     for (int i = 1; i < intervals.length; i++) {         if (intervals[i][1] <= end)             cnt++;         else {             end = intervals[i][1];         }     }     return intervals.length - cnt; }

C++：

public:     int removeCoveredIntervals(vector

 > &intervals) {         // 根據(jù)起始位置，從小到大排序，如果起始位置大小一樣，就根據(jù)指針位置按照從大到小排序。         sort(intervals.begin(), intervals.end(), [](constvector

 &a, constvector

 &b) {             return a[0] == b[0] ? a[1] > b[1] : a[0] < b[0];         });         int end = intervals[0][1];         int cnt = 0;// 刪除的區(qū)間數(shù)量         for (int i = 1; i < intervals.size(); i++) {             if (intervals[i][1] <= end)                 cnt++;             else {                 end = intervals[i][1];             }         }         return intervals.size() - cnt;     }

筆者簡(jiǎn)介

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