專欄：50多種數據結構徹底征服

專欄：50多種經典圖論算法全部掌握

最近一份針對字節跳動豆包大模型負責人喬木的舉報文件在網上流傳，內容是喬木婚內出軌同組HRBP程某，且存在經濟問題（公款攜程某某赴美出差、拒付女兒撫養費等）。

3月28日據多名內部人士透露，喬木和程某的飛書賬號狀態顯示暫停使用，有內部人士表示這意味著公司內部或已啟動調查。

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

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

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

給你一個區間列表，請你刪除列表中被其他區間所覆蓋的區間。只有當 c <= a 且 b <= d 時，我們才認為區間 [a,b) 被區間 [c,d) 覆蓋。

在完成所有刪除操作后，請你返回列表中剩余區間的數目。

示例1：

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

• 1 <= intervals.length <= 1000

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

• 對于所有的 i != j：intervals[i] != intervals[j]

問題分析

這題說的是刪除重疊區間后，返回剩余區間的數量，所謂重疊區間，就是一個區間完全被另一個區間給覆蓋了。

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

如果下一個區間的終點小于等于前一個區間的終點end，說明下一個區間被前一個區間給覆蓋了，要累加覆蓋區間的個數。如果下一個區間的終點大于前一個區間的終點end，說明下個區間沒有覆蓋，要更新end的值。

最后用總的區間數量減去覆蓋的區間數量，就是剩余區間的數量。

JAVA：

public int removeCoveredIntervals(int[][] intervals) {     // 根據起始位置，從小到大排序，如果起始位置大小一樣，就根據指針位置按照從大到小排序。     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;// 刪除的區間數量     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) {         // 根據起始位置，從小到大排序，如果起始位置大小一樣，就根據指針位置按照從大到小排序。         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;// 刪除的區間數量         for (int i = 1; i < intervals.size(); i++) {             if (intervals[i][1] <= end)                 cnt++;             else {                 end = intervals[i][1];             }         }         return intervals.size() - cnt;     }

筆者簡介

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