欧美黑人操逼网站,天天干夜夜夜夜,欧美日韩性爱网,鸡巴美女91,成人做爱在线观看,天天综合网天天综合7799,国内在线视频自拍,久久亚洲综合精品人妻

算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選！

今天和大家聊的問題叫做?無重疊區(qū)間，我們先來看題面：

https://leetcode-cn.com/problems/non-overlapping-intervals/

?Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

給定一個區(qū)間的集合，找到需要移除區(qū)間的最小數(shù)量，使剩余區(qū)間互不重疊。

注意:

可以認(rèn)為區(qū)間的終點(diǎn)總是大于它的起點(diǎn)。

區(qū)間 [1,2] 和 [2,3] 的邊界相互“接觸”，但沒有相互重疊。

示例

示例 1:

輸入: [ [1,2], [2,3], [3,4], [1,3]?]
輸出: 1
解釋: 移除 [1,3]?后，剩下的區(qū)間沒有重疊。

示例 2:

輸入: [ [1,2], [1,2], [1,2]?]
輸出: 2
解釋: 你需要移除兩個 [1,2]?來使剩下的區(qū)間沒有重疊。

示例 3:

輸入: [ [1,2], [2,3]?]
輸出: 0
解釋: 你不需要移除任何區(qū)間，因?yàn)樗鼈円呀?jīng)是無重疊的了。

解題

貪心算法，區(qū)間結(jié)尾越小，留給其他空間的位置越多，能保留更多空間，優(yōu)先保留與當(dāng)前區(qū)域不相交的結(jié)尾最小的區(qū)間

每次選結(jié)尾最小的區(qū)間

將二維數(shù)組按intervals[i][1]從小到大排序，每次取不與當(dāng)前空間相交的end最小的區(qū)間，用區(qū)間總數(shù)-不相交的區(qū)間數(shù)=需刪除的最小區(qū)間數(shù)

class?Solution?{
public:
????int?eraseOverlapIntervals(vector<vector<int>>& intervals)?{
????????if?(intervals.empty()) {
????????????return?0;
????????}
????????
????????sort(intervals.begin(), intervals.end(), [](const?auto& u, const?auto& v) {
????????????return?u[1] < v[1];
????????});

????????int?n = intervals.size();
????????int?right = intervals[0][1];
????????int?ans = 1;
????????for?(int?i = 1; i < n; ++i) {
????????????if?(intervals[i][0] >= right) {
????????????????++ans;
????????????????right = intervals[i][1];
????????????}
????????}
????????return?n - ans;
????}
};