【算法】重载sort的cmp的题

1 406根据身高重建队列

406. 根据身高重建队列

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

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

这个题需要重载sort函数中的cmp。

（1）当身高相同时，ki小的在前面，即身高相同时，ki升序排序；

（2）身高不同时，个子高的人在前面，即按个子降序排序。

（3）排序完后，需要得到每个人在队伍中的位置，即按照ki插入。

class Solution {
public:
    // 重载排序函数
    static bool cmp(const vector<int>& a, const vector<int>& b) {
        // 身高相同，人数少的在前面，即升序
        if (a[0] == b[0]) {
            return a[1] < b[1];
        }
        // 身高不同，高个子人在前面
        return a[0] > b[0];
    }
 
    vectorint>> reconstructQueue(vectorint>>& people) {
        sort(people.begin(), people.end(), cmp);
        listint>> res;
        for (int i = 0; i < people.size(); i++) {
            // 拿到位置
            int position = people[i][1];
            auto it = res.begin();
            // 找到插入的位置
            while (position--) {
                it++;
            }
            res.insert(it, people[i]);
        }
        return vectorint>>(res.begin(), res.end());
    }
};

2 用最少数量的箭引爆气球

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

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

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

给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。

这个题需要重载sort函数中的cmp。

（1）先对气球按起始位置升序排序（终止位置排序也行，起始位置好理解）；

（2）没有交集的气球，直接射一支➹即可；

（3）有交集的气球，更新右边界，注意：右边界是取两者的较小者，等到下次再和下一个气球判断，无交集，射出一支箭；有交集继续更新。

class Solution {
public:
    // 重载排序
    static bool cmp(const vector<int>& a, const vector<int>& b) {
        // 按照起始位置升序排序
        return a[0] < b[0];
    }
 
    int findMinArrowShots(vectorint>>& points) {
        sort(points.begin(), points.end(), cmp);
        int res = 1;             // 至少需要一支箭
        int end = points[0][1];
        for (int i = 1; i < points.size(); i++) {
            // 没有交集
            if (points[i][0] > end) {
                res++;
                end = points[i][1];
            } else {
                end = min(end, points[i][1]);
            }
        }
        return res;
    }
};

3 无重叠区间

435. 无重叠区间

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

（1）本题同样需要重载sort的cmp，这里使用lambda表达式；

（2）这里按照终止位置升序排序，即终止位置小的在前面，这里为什么不按照起始位置升序排序呢？因为终止位置和是下一个起始位置可能重合的区域；

（3）统计重叠区间个数，更新右边界，注意：这里的右边界是取两者的较小者。

class Solution {
public:
    int eraseOverlapIntervals(vectorint>>& intervals) {
        // 使用lambda表达式
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){
            // 按照终止位置升序排序
            return a[1] < b[1];
        });
        int res = 0;                 // 重叠
        int end = intervals[0][1];
        for (int i = 1; i < intervals.size(); i++) {
            // 重叠
            if (end > intervals[i][0]) {
                res++;
                end = min(end, intervals[i][1]);
            } else {
                end = intervals[i][1];
            }
        }
        return res;
    }
};

4 合并区间

56. 合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

（1）按照起始位置升序排序；

（2）判断第i个区间和第i-1个区间是否有重合，如果有重合，则合并，并更新右边界，注意：这里的右边界是取两者的较大者；

（3）这里还需要对最后一个区间进行判断。

class Solution {
public:
    static bool cmp(vector<int>& a, vector<int>& b) {
        // 按照起始位置升序排序
        return a[0] < b[0];
    } 
 
    vectorint>> merge(vectorint>>& intervals) {
        vectorint>> res;
        if (intervals.size() == 0) {
            return res;
        }
        // 排序
        sort(intervals.begin(), intervals.end(), cmp);
        // 标记最后一个区间有没有合并
        bool flag = false;
        int len = intervals.size();
 
        for (int i = 1; i < len; i++) {
            int start = intervals[i - 1][0];         // i-1的左边界
            int end = intervals[i - 1][1];           // i-1的右边界
            // 可以合并
            while (i < len && intervals[i][0] <= end) {
                end = max(end, intervals[i][1]);     // 更新右边界
                // 最后一个区间
                if (i == len - 1) {
                    flag = true;
                }
                i++;
            }
            res.push_back({start, end});
        }
 
        // 如果最后一个区间没有被合并，将其加入到res中
        if (flag == false) {
            res.push_back({intervals[len - 1][0], intervals[len - 1][1]});
        }
        return res;
    }
};

感受：这类题在最开始接触的时候，无从下手，只是有一个感觉，可能要按左或者按右排序，具体怎么排，还真想不到，做了一两道之后，慢慢有点感觉了。