452. 用最少数量的箭引爆气球：代码随想录

这道题目的意思就是你可以垂直的射箭，让你用最少的箭数射完所有的气球，这样其实我们可以很容易的就想到，我们尽可能的去射重叠的气球，这样我们一支箭就可以射多支，所以这里我们可以先对数组进行一个排序，就是可以先考虑到那些重叠在一起的，这题其实题目的要求跟数组元素的顺序无关，排完序后，这里我犯了一个错误就是，我的思路都是对的，就是在判断他们两个气球是不是重叠的时候，其实只要考虑右边界end和下一个气球的左边界就可以了，因为你已经排好序了，这里我将两个气球的左右边界都考虑进去了，所以就写的很复杂，在判断完之后，记得要更新右边界，来看具体的代码的实现

class Solution {
public:
    static bool cmp(pair<int, int> a, pair<int, int> b) {
        return a.first < b.first;
    }
    int findMinArrowShots(vector<vector<int>>& points) {
        int n = points.size();
        pair<int, int> nums[n];
        for (int i = 0; i < n; i++) {
            nums[i].first = points[i][0];
            nums[i].second = points[i][1];
        }
        sort(nums, nums + n, cmp);
        int result = 1; int end = nums[0].second;
        for (int i = 1; i < n; i++) {
            if (nums[i].first <= end) {
                end = min(end, nums[i].second);
            }
            else {
                result++;
                end = nums[i].second;
            }
        }
        return result;
    }
};

在这里我用了一个pair数组，其实你也可以不用，直接用vector也可以，首先就是sort排序，然后就是一开始初始化有边界right，和结果result，只要我当前遍历的这个气球的左边界小于等于我的right，就代表我们是重叠的这样就让right=我们两个右边界的最小值，这样才是判断后面的气球是不是和前面两个重叠，如果不是重叠的，那就直接将result++，然后让我的右边界等于我下一个结点的右边界，就可以了，因为此时我肯定需要另一支箭,这就是这道题目的解答，来看下一道题目

435. 无重叠区间：代码随想录

这道题目的意思就是给你很多个区间，让你求出要去除多少个区间才能保证所有的区间都是不重叠的，其实这道题目和上一道题非常的像，只要你上一道题目弄懂了，这道题稍微改一下就可以了，我们来看具体的代码的实现，

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

主体的代码并没有什么变化，就是if条件判断那里有些细节需要改一下，当重叠的的时候，我们需要将结果加一，然后同样的就是将右边界与这个区间的右边界取一个最小值，那么为什么要取最小值呢，你稍微想想就知道，如果我取大的话，那么后面的是不是更容易发生重叠啊，所以这里我们就是要选取更小的那个，同样的如果说不重叠的话，那就是直接让右边界等于下一个的右边界就可以了，直到数组遍历完，再返回结果即可。下面来看第三题

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