代码随想录算法训练营DAY36|C++贪心算法Part.5|435.无重叠区间、763.划分字母区间、56. 合并区间

435.无重叠区间

力扣题目链接

文章链接：435.无重叠区间

视频链接：贪心算法，依然是判断重叠区间 | LeetCode：435.无重叠区间

状态：排序顺序很重要！决定了我们如何处理后续逻辑。对于按右边界排序，我们只要抓住分割线即可，每次更新分割线，说明就有非交叉区间；

想都不用想，本题首先要求的肯定就是进行排序，让为了让我们后续更好进行操作。

并且可以很直观得推导出我们的贪心策略：

局部最优——当前区间与相邻两个区间是否重叠，这里是非常有技巧的，具体可以看下面的思路

全局最优——找出所有的重叠区间

按右边界排序

我们先按右边界进行排序，然后从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了。

在记录非交叉区间的个数也是很需要技巧的：

总之一句话，最重要的点就在于找到区间的分割线，每次遇到分割线，我们就记录一次非交叉区间个数。比如上文中，更新了两次分割线，所以非交叉区间是3。所以在代码表现上，也是比较直观的。
基于以上代码的一个重要前提就是：区间是按照右边界来排序的

CPP代码

class Solution {
public:
    // 按照区间右边界排序
    static bool cmp (const vector& a, const vector& b) {
        return a[1] < b[1];
    }
    int eraseOverlapIntervals(vector>& intervals) {
        if (intervals.size() == 0) return 0;
        sort(intervals.begin(), intervals.end(), cmp);
        int count = 1; // 记录非交叉区间的个数
        int end = intervals[0][1]; // 记录区间分割点
        for (int i = 1; i < intervals.size(); i++) {
            if (end <= intervals[i][0]) {	//与每个区间的左边界比较
                end = intervals[i][1];		//更新分割线
                count++;
            }
        }
        return intervals.size() - count;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

按左边界排序

对于左边界排序，这里拿 intervals = [[1,100],[11,22],[1,11],[2,12]]举例，

排序后：intervals = [[1,100],[1,11],[2,12],[11,22]]。如果我们按照右边界排序的处理还能行吗。简单推导一下，这样会导致我们的最终结果是3！因为end永远都无法更新，程序认为只有一条分割线，也就是count = 1。

那么如果按照左边界来排序应该怎么写呢？

如何判断相邻区间是否重叠

如果当前区间的左边界[1, 11]大于等于上一个区间的右边界[1, 100]。说明相邻区间不重叠，如果不满足该情况，那肯定说明区间重叠。
这里的count表示的是重叠区间的个数。
end在此处仍然表示的是区间分割点。

if (intervals[i-1][0] >= intervals[i][1]) end = intervals[i][1];
else {
   count++; //记录我们重叠了多少个区间
}
1
2
3
4

如何判断一下一个区间与当前相邻区间是否重叠

要首先计算出之前我们判断的相邻区间的最小边界（左边界的最小值），和我们下一个区间的左边界是否重叠。

else {
  count++;
  end = min(end, intervals[i][1])
}
1
2
3
4

这里num[i][1]=min(nums[i-1][1], nums[i][1])，等到i遍历到下一个区间，应该和之前两个相邻区间的最小右边界比较，如果当前i区间的左边界要大的话，那么说明不是重叠区间。

总结

左边界的思想一句话就是：如果发现了重叠区间，我们就进行更新新的分割点，并且count++

CPP代码

class Solution {
public:
    static bool cmp (const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0]; // 改为左边界排序
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (intervals.size() == 0) return 0;
        sort(intervals.begin(), intervals.end(), cmp);
        int count = 0; // 注意这里从0开始，因为是记录重叠区间
        int end = intervals[0][1]; // 记录区间分割点
        for (int i = 1; i < intervals.size(); i++) {   
            if (intervals[i][0] >= end)  end = intervals[i][1]; // 无重叠的情况
            else { // 重叠情况 
                end = min(end, intervals[i][1]);
                count++;
            }
        }
        return count;
    }
};

# 精简版
class Solution {
public:
    static bool cmp (const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0]; // 改为左边界排序
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (intervals.size() == 0) return 0;
        sort(intervals.begin(), intervals.end(), cmp);
        int count = 0; // 注意这里从0开始，因为是记录重叠区间
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] < intervals[i - 1][1]) { //重叠情况
                intervals[i][1] = min(intervals[i - 1][1], intervals[i][1]);
                count++;
            }
        }
        return count;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

763.划分字母区间

力扣题目链接

文章链接：763.划分字母区间

视频链接：贪心算法，寻找最远的出现位置！ LeetCode：763.划分字母区间

状态：

本题其实就是一句话“面多了加水，水多了加面，直到刚刚好”。

这里完全不是贪心的思路，就是全局的一个模拟，主要它也属于重叠区间的问题。

思路

思路上还是很难想到的。

我们在遍历过程中，相当于找到每一个字母出现的边界，如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点了。

所以分为如下两步：

• 统计每个字符最后出现的位置
• 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点

我们需要记录每个字符出现的最后位置，如图：

伪代码实现

• 统计每一个字符最后出现的位置

int hash[27] = {0}; //i为字符，hash[i]为字符出现的最后位置
for (int i = 0; i < S.size(); ++i) {
  hash[S[i] - 'a'] = i;
}
1
2
3
4

• 定义变量

vector<int> result;
int left = 0;
int right = 0;
1
2
3

• 字符出现的最远边界的更新和结果存储

for (int i = 0; i < S.size(); i++) {
    right = max(right, hash[S[i] - 'a']); // 找到字符出现的最远边界
    if (i == right) {
        result.push_back(right - left + 1);
        left = i + 1;
    }
}
1
2
3
4
5
6
7

CPP代码

class Solution {
public:
    vector<int> partitionLabels(string S) {
        int hash[27] = {0}; // i为字符，hash[i]为字符出现的最后位置
        for (int i = 0; i < S.size(); i++) { // 统计每一个字符最后出现的位置
            hash[S[i] - 'a'] = i;
        }
        vector<int> result;
        int left = 0;
        int right = 0;
        for (int i = 0; i < S.size(); i++) {
            right = max(right, hash[S[i] - 'a']); // 找到字符出现的最远边界
            if (i == right) {
                result.push_back(right - left + 1);
                left = i + 1;
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

56. 合并区间

力扣题目链接

文章链接：56. 合并区间

视频链接：贪心算法，合并区间有细节！LeetCode：56.合并区间

状态：

思路

本题同样也是重叠区间的问题。

区别在于判断区间重叠后的逻辑，本题是将重叠区间进行合并。

先排序，如果intervals[i][0] <= intervals[i - 1][1]就有重叠，所以进行合并

合并的逻辑也比较简单，

用合并区间后左边界和右边界，作为一个新的区间，加入到result数组里就可以了。如果没有合并就把原区间加入到result数组。

CPP代码

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> result;
        if (intervals.size() == 0) return result; // 区间集合为空直接返回
        // 排序的参数使用了lambda表达式
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){return a[0] < b[0];});

        // 第一个区间就可以放进结果集里，后面如果重叠，在result上直接合并
        result.push_back(intervals[0]); 

        for (int i = 1; i < intervals.size(); i++) {
            if (result.back()[1] >= intervals[i][0]) { // 发现重叠区间
                // 合并区间，只更新右边界就好，因为result.back()的左边界一定是最小值，因为我们按照左边界排序的
                result.back()[1] = max(result.back()[1], intervals[i][1]); 
            } else {
                result.push_back(intervals[i]); // 区间不重叠 
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22