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

我不是女神ヾ 2022-12-03 13:22 132阅读 0赞

### 题目 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE3MjYwMDU_size_16_color_FFFFFF_t_70_pic_center]![在这里插入图片描述][20200903222216935.png_pic_center]

### 解答 ###

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE3MjYwMDU_size_16_color_FFFFFF_t_70_pic_center 1]

气球\[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;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE3MjYwMDU_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200903222206303.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE3MjYwMDU=,size_16,color_FFFFFF,t_70#pic_center
[20200903222216935.png_pic_center]: /images/20221123/bb54775d3a4140baa1d41d2b2ebea80d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE3MjYwMDU_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/e85a216d0bd349eea853c884c28a5b7b.png