406. 根据身高重建队列

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

示例 1：

输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
解释：
编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。

分析：

本来这道题想着是用排列的方式，先排个序，让 ki 小的放前面，然后进行深搜，结果发现超时了。 

class Solution {
public:

    vector<vector<int>> ans;
    vector<bool> used;

    static bool cmp(vector<int> a, vector<int> b) {
        if (a[1] == b[1]) return a[0] < b[0];
        else return a[1] < b[1];
    }

    bool isValid(vector<vector<int>>& people, int id) {
        int front = 0;
        for (int i = 0; i < ans.size(); ++i) {
            if (ans[i][0] >= people[id][0]) ++front;
        }
        return front == people[id][1];
    }

    bool traceback(vector<vector<int>>& people) {
        if (ans.size() == people.size()) return true;
        for (int i = 0; i < people.size(); ++i) {
            if (used[i]) continue;
            if (isValid(people, i)) {
                used[i] = true;
                ans.push_back(people[i]);
                if (traceback(people)) return true;
                ans.pop_back();
                used[i] = false;
            }
        }
        return false;
    }

    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        used.resize(people.size(), false);
        sort(people.begin(), people.end(), cmp);
        traceback(people);
        return ans;
    }
};

 分析：

在之前的思路中，考虑的是使用 ki 排序，然后根据顺序去做插入，其实根据 ki 排序的效果并不佳，因为他既没有确定身高的顺序，后续在使用 ki 时也没有起到多大作用。当有两个维度去思考问题时，一种不行就要考虑另外一种，也就是 hi 。

我们将 hi 从高到低排序，如果 hi 相同，那么将 ki 从小到大排序。这样就很方便后面操作，我们只需要将元素依次按照顺序插入到 ki 的位置即可，因为按照身高排好序的元素本身已经满足了前面的元素比本元素高的要求。过程如下：

排序完的people： [[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]]

插入过程：

[[7,0]]

[[7,0], [7,1]]

[[7,0], [6,1], [7,1]]

[[5,0], [7,0], [6,1], [7,1]]

[[5,0], [7,0], [5,2], [6,1], [7,1]]

[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

class Solution {
public:

    vector<vector<int>> ans;
    vector<bool> used;

    static bool cmp(vector<int> a, vector<int> b) {
        if (a[0] == b[0]) return a[1] < b[1];
        else return a[0] > b[0];
    }

    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), cmp);
        vector<vector<int>> ans;
        for (int i = 0; i < people.size(); ++i) {
            int index = people[i][1];
            ans.insert(ans.begin()+index, people[i]);
        }
        return ans;
    }
};

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

在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以纵坐标并不重要，因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。

一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足  xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。

给你一个数组 points ，其中 points [i] = [xstart,xend] ，返回引爆所有气球所必须射出的最小弓箭数。

 
示例 1：

输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：对于该样例，x = 6 可以射爆 [2,8],[1,6] 两个气球，以及 x = 11 射爆另外两个气球

分析：

这题乍一看就像是 最短日程安排 那类题目，具体思路：首先按照右边界进行排序，然后接下来的气球只要左边界小于当前右边界的就可以一起射破，否则需要一根新的箭。

这题最大的坑点在于排序时需要加引用，这样才会快，不然最后有个样例过不了，会超时。 

class Solution {
public:

    static bool cmp (vector<int>& a, vector<int>& b) {
        return a[1] < b[1];
    }

    int findMinArrowShots(vector<vector<int>>& points) {
        sort(points.begin(), points.end(), cmp);
        int ans = 0, i = 0, size = points.size();
        while(i < size) {
            ++ans;
            int board = points[i][1];
            while(i < size && board >= points[i][0]) ++i;
        }
        return ans;
    }
};

 435. 无重叠区间

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

注意:

可以认为区间的终点总是大于它的起点。
区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。
示例 1:

输入: [ [1,2], [2,3], [3,4], [1,3] ]

输出: 1

解释: 移除 [1,3] 后，剩下的区间没有重叠。

分析：

这个题就相当于上面那个题的变形，我们只需要找到重叠区间的个数，然后用总数目-重叠区间的个数就是需要移除的区间数目。 

 

class Solution {
public:

    static bool cmp (vector<int>& a, vector<int>& b) {
        return a[1] < b[1];
    }

    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), cmp);
        int ans = 0, i = 0;
        while(i < intervals.size()) {
            ++ans;
            int board = intervals[i][1];
            while(i < intervals.size() && intervals[i][0] < board) ++i;
        }
        return intervals.size()-ans;
    }
};