力扣-根据身高重建队列 & 用最少数量的箭引爆气球

406. 根据身高重建队列

class Solution {
public:
    static bool cmp(vector<int> &a, vector<int> &b)
    {
        if(a[0] != b[0])//如果第一个数不相等，也就是身高不相等
        {
            return a[0] > b[0];//按从大到小排
        }
        else//如果身高相等，那就排第二个数
        {
            return a[1] < b[1];//按从小到大排//为的就是先往结果里插 身高最高 而且 前面比他高的人数最少 的人
        }
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        //先排序
        sort(people.begin(), people.end(), cmp);
        //开始插入
        vector<vector<int>> ans;
        //遍历people每个人
        for(int i = 0; i < people.size(); i++)
        {
            ans.insert(ans.begin() + people[i][1], people[i]);
        }
        return ans;
    }
};

    简单的贪心策略，先按身高从大到小排序，身高一样了按第二个值从小到大排序，然后遍历依次插入相应位置。

    要注意的是：cmp函数形参要写vector，不能写pair<int, int>，不然会报错。

    顺便记录下vector中insert的用法

insert用法

语法：

iterator insert( iterator loc, const TYPE &val );

void insert( iterator loc, size_type num, const TYPE &val );

void insert( iterator loc, input_iterator start, input_iterator end );

解释：

• 在指定位置loc前插入值为val的元素,返回指向这个元素的迭代器,
• 在指定位置loc前插入num个值为val的元素
• 在指定位置loc前插入区间[start, end)的所有元素 .

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

class Solution {
public:
    static bool cmp(vector<int> &a, vector<int> &b)
    {
        return a[0] < b[0];
    }
    //贪心，局部最优推出全局最优，每支箭尽可能地多射气球
    int findMinArrowShots(vector<vector<int>>& points) {
        //先按气球左边界从小到大排序
        sort(points.begin(), points.end(), cmp);
        //第一个气球一定是要用一只箭打到的
        int cnt = 1;//记录箭矢的数量
        int minEnd = points[0][1];//记录每一组气球的最小右边界
        //遍历所有气球
        for(int i = 1; i < points.size(); i++)
        {
            //判断这个气球能否和这一组气球们用一只箭打下来
            //当这支箭的左边界超过这组气球的最小右边界时
            if(points[i][0] > minEnd)
            {
                //这个气球就成了下一组的第一个气球
                cnt++;//需要多一支箭
                minEnd = points[i][1];//新一组气球的最小右边界
            }
            //如果能加入这组气球，比如第二个气球的左边界就小于第一个气球的右边界
            //那么右边界要时刻尝试更新
            minEnd = min(points[i][1], minEnd);
        }
        return cnt;
    }
};

    这道题需要注意的点还挺多的。

1. 核心点：贪心策略怎么贪？

    需要先把气球排好序，然后从第一个气球开始，尽可能地每一箭射中（包括第一个）最多的气球，这样局部最优推出全局最优。

2. 怎么排？

    按气球的左边界从小到大排就行了

3. 注意点：最小右边界

    排序过后可以保证下一个气球的左边界一定大于等于上一个气球的左边界，那么这个气球是否能够加入上一组气球中一起射中，就要看这个气球的右边界了。

    如果这个气球的右边界小于等于上一组所有气球中的最小右边界也就是类似这样:

   （（ （））），中间的（）是这个气球，那么这个气球就可以加入到上一组。

    如果这个气球的左边界大于上一组气球中的最小右边界，也就是这样：

   （（ ）{） }，花括号作为这个气球， 可以看到此时一箭不能射中三个气球了，必须再多射一箭了。