[LeetCode]Minimum Number of Arrows to Burst Balloons

这道题和Non-overlapping Intervals是一样。首先个根据EFT算法我们找到集合中最多的不重叠的intervals，假设有k个。那么我们所用的飞镖数不可能比这个再少了，因为对于这k个气球，我们无论如何也要用k个飞镖戳破，因为他们彼此之间不重合。那么对于剩下的气球，根据EFT的算法，任何一个气球都和这k个当中某一个重合，随意最优解就是k。具体算法参见链接的那篇文章，时间复杂度O(nlogn)，代码如下:

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

view raw Minimum Number of Arrows to Burst Balloons.cpp hosted with ❤ by GitHub