452. Minimum Number of Arrows to Burst Balloons

素颜马尾好姑娘i 2022-03-21 11:54 147阅读 0赞

There are a number of spherical balloons spread in two-dimensional space. For each balloon, provided input is the start and end coordinates of the horizontal diameter. Since it's horizontal, y-coordinates don't matter and hence the x-coordinates of start and end of the diameter suffice. Start is always smaller than end. There will be at most 104 balloons.

An arrow can be shot up exactly vertically from different points along the x-axis. A balloon with xstart and xend bursts by an arrow shot at x if xstart ≤ x ≤ xend. There is no limit to the number of arrows that can be shot. An arrow once shot keeps travelling up infinitely. The problem is to find the minimum number of arrows that must be shot to burst all balloons.

**Example:**

Input:
    [[10,16], [2,8], [1,6], [7,12]]
    
    Output:
    2
    
    Explanation:
    One way is to shoot one arrow for example at x = 6 (bursting the balloons [2,8] and [1,6]) and another arrow at x = 11 (bursting the other two balloons).

题意：已知在一个平面上有**一定数量**的气球，平面可以看做是一个**坐标系**，在平面**x轴**的不同位置安排弓箭手想向**y轴方向**射箭，弓箭可以向y轴走**无穷远**，给定气球的宽度 xstart <= x <= xend，问至少需要多少弓箭手，将全部气球打爆？

分析：（1）对于某个气球，**至少需要**使用**1只弓箭**将它击穿；（2）在这只气球将其击穿的同时，尽可能击穿其它更多的气球！（贪心）

算法：（1）对各个气球进行**排序**，按照气球的左端点**从小到大**排序（2）遍历气球数组，同时维护一个**射击区间**，在满足可以将当前气球射穿的情况下，尽可能击穿**更多**的气球，每击穿一个新的气球，**更新**一次射击区间（保证射击区间可以将新气球也击穿）（3）如果新的气球没办法被击穿了，则需要**增**加一名弓箭手，即维护一个**新的**射击区间（将该气球击穿），随后继续遍历气球数组。

class Solution {
    public:
    	int findMinArrowShots(vector<pair<int, int>>& points) {
    		if (points.size() <= 1)
    			return  points.size();
    		sort(points.begin(), points.end());
    
    		pair<int, int> index = points[0];
    		int count = 1;
    		for (int i = 1; i < points.size(); i++)
    		{
    			if (points[i].first <= index.second)
    			{
    				index.first = points[i].first;
    				if (points[i].second < index.second)
    					index.second = points[i].second;
    			}
    			else
    			{
    				count++;
    				index = points[i];
    			}
    		}
    	return count;
    	}
    };