Top Interview 150 P452 Minimum Number of Arrows to Burst Balloons

---

timeline

timeline

2025-11-18

init

Interval

---

Problem:

P452 Minimum Number of Arrows to Burst Balloons

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

This problem is essentially about finding how many independent intersections the intervals have. You can slightly modify the previous P56 Merge Intervals, merging [1,3] and [2,4] into [2,3], taking the tighter boundaries, and then count the number of vectors.

#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();
	}
};