【贪心】 LeetCode452. 用最少数量的箭引爆气球

题目

解答

数形结合，将气球画到坐标系里面。从左往右遍历气球，用一支箭尽可能地射中最多的气球，也就是在一个交集中有最多的气球。

气球[1, 6], [2, 7], [3, 4], [8, 12], [10, 11] 从左到右不断地找到最小的交集，[1, 6]和[2, 7]的交集为[2, 6]，[2, 6]和[3, 4]的交集为[3, 4]，[3, 4]和[8, 12]无交集，那么气球[1, 6], [2, 7], [3, 4]的最交集为[3, 4]，这三个气球用一根箭。后面的气球同理找到交集[10, 11]，那么[8, 12]和 [10, 11]这两个气球用一根箭。

代码

#include <iostream> #include <string> #include <list> #include <vector> #include <map> #include <functional> #include <algorithm> #include <utility> #include <cassert> // 452. Minimum Number of Arrows to Burst Balloons typedef std::pair<int, int> Point; // 贪心。 // 数形结合，用最简单的情况画出坐标图，然后进行找规律。 int findMinArrowShots(std::vector<Point>& points) { if (points.empty()) { return 0; } std::sort(points.begin(), points.end(), [](const Point& lhs, const Point& rhs) { return lhs.first < rhs.first; }); int arrow_sum = 1; int right_point = points[0].second; for (std::size_t i = 1; i < points.size(); ++i) { const Point& point = points[i]; if (right_point >= point.first) { if (right_point > point.second) { right_point = point.second; } continue; } ++arrow_sum; right_point = point.second; } return arrow_sum; } void PrintPoints(const std::vector<Point>& points) { for (const Point& point : points) { std::cout << point.first << "," << point.second << std::endl; } } void TestCase1() { std::vector<Point> points; points.push_back(std::make_pair(10, 16)); points.push_back(std::make_pair(2, 8)); points.push_back(std::make_pair(1, 6)); points.push_back(std::make_pair(7, 12)); PrintPoints(points); std::cout << findMinArrowShots(points) << std::endl; PrintPoints(points); std::cout << "---------------------" << std::endl; } void TestCase2() { std::vector<Point> points; points.push_back(std::make_pair(9,12)); points.push_back(std::make_pair(1,10)); points.push_back(std::make_pair(4,11)); points.push_back(std::make_pair(8,12)); points.push_back(std::make_pair(3,9)); points.push_back(std::make_pair(6,9)); points.push_back(std::make_pair(6,7)); PrintPoints(points); std::cout << findMinArrowShots(points) << std::endl; PrintPoints(points); std::cout << "---------------------" << std::endl; } int main() { TestCase1(); TestCase2(); return 0; }