【代码随想录第30天| 452. 用最少数量的箭引爆气球，435. 无重叠区间，763.划分字母区间 】

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

重叠区间问题，先按一端排序，然后只关注另一端即可

思路

• 自己的思路：什么时候进行result++十分关键

代码随想录

class Solution {
public:
    static bool cmp(const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    }
    int findMinArrowShots(vector<vector<int>>& points) {
        int result = 1;
        int end = INT32_MAX;
        sort(points.begin(), points.end(), cmp);
        for (int i = 0; i < points.size(); i++) {
            end = min(end, points[i][1]);
            if (points[i][0] > end) {   // 什么时候进行 result++ 很关键
                result++;
                end = points[i][1];
                continue;
            } else {
                continue;
            }
        }
        return result;
    }
};

435. 无重叠区间

思路

• 思路类似，也是先排序
• 贪心思想：优先剔除右边界比较大的区间，即将右边界更新为重叠区间二者间较小的值。

代码随想录

class Solution {
public:
    static bool cmp(vector<int>& a, vector<int>& b) {
        return a[0] < b[0];
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), cmp);
        int result = 0;
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] < intervals[i-1][1]) {
                result ++;
                intervals[i][1] = min(intervals[i][1], intervals[i-1][1]);
            } else {
                continue;
            }
        }
        return result;
    }
};

763.划分字母区间

思路

• 这道题思路一开始没想到，先用一个循环和hash[s[i] - 'a']获得每一个字母出现的最远位置。
• 用left和right记录临时区间的左右边界，并使用right实时更新该区间的最大边界值，当循环到这个最大边界值时，push_back(right - left + 1)。

代码随想录

class Solution {
public:
    vector<int> partitionLabels(string s) {
        vector<int> result;
        int hash[26] = {0};
        for (int i = 0; i < s.length(); i++) {
            hash[s[i] - 'a'] = i;
        }
        int right = 0;
        int left = 0;
        for (int i = 0; i < s.length(); i++) {
            // 如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点了
            right = max(right, hash[s[i] - 'a']);
            if (i == right) {
                result.push_back(right - left + 1);
                left = i + 1;
            }
        }
        return result;
    }
};