56-区间合并

LeetCode 56. Merge Intervals

LeetCode-56

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]

method: 模拟

先按左区间排序，左区间相同再按右区间排序
如果后一个区间的左区间小于当前区间的右区间，就可以合并，取两个区间的右区间的较大值

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end());   // 区间排序
    vector<vector<int>> res;
    res.push_back(intervals[0]);
    for (int i = 1; i < intervals.size(); i++) {
        if (intervals[i][0] <= res.back()[1])   // 可以合并
            res.back()[1] = max(res.back()[1], intervals[i][1]);
        else 
            res.push_back(intervals[i]);
    }
    return res;
}

---

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

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

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

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

示例 1：

输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：气球可以用2支箭来爆破:
-在x = 6处射出箭，击破气球[2,8]和[1,6]。
-在x = 11处发射箭，击破气球[10,16]和[7,12]。

method

类似于区间合并，不过要取右端点的较小值，小于这个较小值才能引爆

int findMinArrowShots(vector<vector<int>>& points) {
    sort(points.begin(), points.end());
    int res = 1;
    for (int i = 1; i < points.size(); i++) {
        if (points[i][0] > points[i - 1][1]) {
            res++;
        } else {
            points[i][1] = min(points[i - 1][1], points[i][1]);
        }
    }
    return res;
}