面试经典150题 P452 用最少数量的箭引爆气球

---

时间轴

时间轴

2025-11-18

init

区间

---

题目：

P452 用最少数量的箭引爆气球

https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/description/?envType=study-plan-v2&envId=top-interview-150

这个题实际上是求区间有多少个独立的交集。可以略微改动前面的 P56 合并区间，把[1,3],[2,4]合并成[2,3]，取更缩紧的边界，然后再统计vector个数即可。a

#include <vector>
#include <algorithm>
using std::vector;

class Solution {
    public:
	int findMinArrowShots(vector<vector<int> > &points)
	{
		int curr_left, curr_right, last_left, last_right;			  
		vector<vector<int> > res_vec;
		vector<int> last;

		std::sort(points.begin(), points.end(),
			  [](vector<int> &vec1, vector<int> &vec2) { return vec1[0] < vec2[0]; });
		
		
		for (vector<int> &point : points) {
			curr_left = point[0];
			curr_right = point[1];
			if (last.empty()) {
				res_vec.push_back({ curr_left, curr_right });
				last = res_vec.back();
			} else {
				last_left = last[0];
				last_right = last[1];
				if (curr_left > last_right) {
					res_vec.push_back({ curr_left, curr_right });
					last = res_vec.back();
				} else { // else if (curr_left <= last_right) {
					res_vec.pop_back();
					res_vec.push_back({ curr_left, std::min(curr_right, last_right) });
					last = res_vec.back();
				}
			}
		}

		return res_vec.size();
	}
};