立志重刷代码随想录60天冲冲冲！！——第三十天

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

class Solution {
public:
    bool static cmp (vector<int>a, vector<int>b) {
        return a[0] < b[0];
    }
    int findMinArrowShots(vector<vector<int>>& points) {
        int res = 1; // 最少需要一支箭
        if (points.size() == 0) return res;
        sort(points.begin(), points.end());
        for (int i = 1; i < points.size(); i++) {
            // 如果i的左边界 > i-1的右边界，就射箭
            if (points[i][0] > points[i - 1][1]) {
                res++;
            } else {
                // 如果i的左边界 <= i-1的右边界，更新最小的右边界
                points[i][1] = min(points[i][1], points[i - 1][1]);
            }
        }
        return res;
    }
};

435. 无重叠区间

class Solution {
public:
    bool static cmp (vector<int>a, vector<int>b) {
        return a[0] < b[0];
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        int res = 0;
        if (intervals.size() == 1) return res;
        sort(intervals.begin(), intervals.end(), cmp);

        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] < intervals[i-1][1]) {
                res++;
                intervals[i][1] = min(intervals[i-1][1], intervals[i][1]);
            }
        }        
        return res;
    }
};

763.划分字母区间

class Solution {
public:
    vector<int> partitionLabels(string s) {
        vector<int> res;
        vector<int> hashtable(26,0);
        // 1、 遍历数组，得到每个元素的最远索引
        for (int i = 0; i < s.size(); i++) {
            hashtable[s[i] - 'a'] = i;
        }
        // 2、 双指针，寻找分割点
        int idx = 0;
        int left = 0;
        for (int i = 0; i < s.size(); i++) {
            idx = max(idx, hashtable[s[i] - 'a']); // 注意哈希表的取值
            if (idx == i) {
                res.push_back(i - left + 1);
                left = i + 1;
            }
        }
        return res;
    }
};