贪心算法之重叠区间问题

以下四个题都是重叠区间问题

452. 用最少数量的箭引爆气球

• 为了让气球尽可能重叠，先按照气球起始位置由大到小排序
• tips：sort默认就可以实现以上排序，不需要写cmp
• 重点：当下一个气球的左边界不小于上一个气球的右边界时(即有重叠的情况)，为了判断再下一个气球能否和这两个有重叠，就需要将右边界 point[i][1] 置成小的那个右边界 min(point[i-1][1] , point[i][1])

class Solution {
public:int findMinArrowShots(vector<vector<int>>& points) {sort(points.begin(), points.end());int ret = 1;for (int i = 1; i < points.size(); i++) {if (points[i][0] > points[i - 1][1]) ret++;else points[i][1] = min(points[i - 1][1], points[i][1]);}return ret;}
};

435. 无重叠区间

与上一个题极其相似，首先按照左边界排序，当重叠的时候，舍弃重叠的右边长的那个区间(即将右边界定为小的那个)，ret++记录重叠区间个数。

class Solution {
public:int eraseOverlapIntervals(vector<vector<int>>& intervals) {sort(intervals.begin(), intervals.end());int ret = 0;for (int i = 1; i < intervals.size(); i++) {if (intervals[i][0] < intervals[i - 1][1]) {ret++;intervals[i][1] = min(intervals[i][1], intervals[i - 1][1]);}}return ret;}
};

763. 划分字母区间

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

class Solution {
public:vector<int> partitionLabels(string s) {int hash[27] = {0};for (int i = 0; i < s.size(); i++) {hash[s[i] - 'a'] = i;}vector<int> ret;int left = 0, right = 0;for (int i = 0; i < s.size(); i++) {right = max(hash[s[i] - 'a'], right);if (right == i) {ret.push_back(right - left + 1);left = i + 1;}}return ret;}
};

56. 合并区间

和上面的435差不多，先按照左边界排序好，将第一组数据添加到ret中，之后如果满足后一个的左边界小于等于这个的右边界时候，更新ret中的这个(ret.back()[1]更新成大的右边界)，不满足就把下一个添加进来，for循环是从i=1开始

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {sort(intervals.begin(), intervals.end());if (intervals.size() == 1)return intervals;vector<vector<int>> ret;ret.push_back(intervals[0]);for (int i = 1; i < intervals.size(); i++) {if (intervals[i][0] <= ret.back()[1]) {ret.back()[1] = max(ret.back()[1], intervals[i][1]);} elseret.push_back(intervals[i]);}return ret;}
};