專欄：50多種數(shù)據(jù)結(jié)構(gòu)徹底征服
專欄：50多種經(jīng)典圖論算法全部掌握
最近一份針對字節(jié)跳動(dòng)豆包大模型負(fù)責(zé)人喬木的舉報(bào)文件在網(wǎng)上流傳，內(nèi)容是喬木婚內(nèi)出軌同組HRBP程某，且存在經(jīng)濟(jì)問題（公款攜程某某赴美出差、拒付女兒撫養(yǎng)費(fèi)等）。
3月28日據(jù)多名內(nèi)部人士透露，喬木和程某的飛書賬號狀態(tài)顯示暫停使用，有內(nèi)部人士表示這意味著公司內(nèi)部或已啟動(dòng)調(diào)查。
喬木畢業(yè)于西安交大，2014年加入字節(jié)跳動(dòng)，他的妻子羅某某也是西安交大的本科生，中山大學(xué)碩士，有兩個(gè)女兒一個(gè)3歲，一個(gè)8歲。網(wǎng)上的傳言比較多，下面是我用豆包的提問，已經(jīng)簡要概述了。
--------------下面是今天的算法題--------------
來看下今天的算法題，這題是LeetCode的第1288題：刪除被覆蓋區(qū)間，難度是中等。
給你一個(gè)區(qū)間列表，請你刪除列表中被其他區(qū)間所覆蓋的區(qū)間。只有當(dāng) c <= a 且 b <= d 時(shí)，我們才認(rèn)為區(qū)間 [a,b) 被區(qū)間 [c,d) 覆蓋。
在完成所有刪除操作后，請你返回列表中剩余區(qū)間的數(shù)目。
示例1：
輸入：intervals = [[1,4],[3,6],[2,8]] 輸出：2 解釋：區(qū)間 [3,6] 被區(qū)間 [2,8] 覆蓋，所以它被刪除了。
1 <= intervals.length <= 1000
0 <= intervals[i][0] < intervals[i][1] <= 10^5
對于所有的 i != j：intervals[i] != intervals[j]
問題分析
這題說的是刪除重疊區(qū)間后，返回剩余區(qū)間的數(shù)量，所謂重疊區(qū)間，就是一個(gè)區(qū)間完全被另一個(gè)區(qū)間給覆蓋了。
我們先對所有區(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，說明下一個(gè)區(qū)間被前一個(gè)區(qū)間給覆蓋了，要累加覆蓋區(qū)間的個(gè)數(shù)。如果下一個(gè)區(qū)間的終點(diǎn)大于前一個(gè)區(qū)間的終點(diǎn)end，說明下個(gè)區(qū)間沒有覆蓋，要更新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; }
筆者簡介
博哥，真名：王一博，畢業(yè)十多年， 作者，專注于 數(shù)據(jù)結(jié)構(gòu)和算法 的講解，在全球30多個(gè)算法網(wǎng)站中累計(jì)做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨(dú)特的解題思路和解題技巧，喜歡的可以給個(gè)關(guān)注，也可以 下載我整理的1000多頁的PDF算法文檔 。
熱門跟貼