贪心算法之重叠区间问题

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

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;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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]);
            } else
                ret.push_back(intervals[i]);
        }
        return ret;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18