leetcode 452) Minimum Number of Arrows to Burst Balloons

LV. Medium 🧐

https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/

Minimum Number of Arrows to Burst Balloons - LeetCode

 

문제

There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array points where points[i] = [xstart, xend] denotes a balloon whose horizontal diameter stretches between xstart and xend. You do not know the exact y-coordinates of the balloons.

Arrows can be shot up directly vertically (in the positive y-direction) from different points along the x-axis. A balloon with xstart and xend is burst by an arrow shot at x if xstart <= x <= xend. There is no limit to the number of arrows that can be shot. A shot arrow keeps traveling up infinitely, bursting any balloons in its path.

Given the array points, return the minimum number of arrows that must be shot to burst all balloons.

 

Example 1:

Input: points = [[10,16],[2,8],[1,6],[7,12]]
Output: 2
Explanation: The balloons can be burst by 2 arrows:
- Shoot an arrow at x = 6, bursting the balloons [2,8] and [1,6].
- Shoot an arrow at x = 11, bursting the balloons [10,16] and [7,12].

Example 2:

Input: points = [[1,2],[3,4],[5,6],[7,8]]
Output: 4
Explanation: One arrow needs to be shot for each balloon for a total of 4 arrows.

Example 3:

Input: points = [[1,2],[2,3],[3,4],[4,5]]
Output: 2
Explanation: The balloons can be burst by 2 arrows:
- Shoot an arrow at x = 2, bursting the balloons [1,2] and [2,3].
- Shoot an arrow at x = 4, bursting the balloons [3,4] and [4,5].

 

Constraints:

• 1 <= points.length <= 10^5
• points[i].length == 2
• -2^31 <= xstart < xend <= 2^31 - 1

 

문제 해결법

일단 풍선들의 x좌표의 순서가 복잡하게 들어오기 때문에, sort 함수를 활용해서 x0를 기준으로 오름차순으로 정렬해줬다

2차원 백터를 정렬하기 위해 compare라는 함수를 만들어 sort의 마지막 인자에 넣어줬다

(sort는 <algorithm> 헤더 안에 정의되어 있음)

 

start : 현재 공통 범위의 시작 지점

end : 현재 공통 범위의 끝 지점

 

백터를 추가할 때마다 start = max(start, points[i][0])이고, end = min(start, points[i][1])이다

이해가 안 된다면 밑의 그림에 첫 번째 풍선, 두 번째 풍선에 대입해서 보면 이해가 될 것이다

 

위의 방식대로 진행하다가 현재 백터와 공통 범위가 겹치는 구간이 없다면 end < start가 된다

밑의 그림을 보면 두 번째 풍선과 세 번째 풍선의 상황이다

이 경우 공통 범위를 넘어갔기 때문에 화살을 추가로 이용해야 되는 상황이므로, ans++를 하고 start = points[i][0], end = points[i][1]로 업데이트해준다 -> 새로운 공통 범위 시작

그림이 너무 더러워도 이해하고 봐주길..

 

compare에 파라미터를 vector<int>a라고 했을 때는 타임 익시드가 떴다..

복사해서 보내느라 많은 시간을 쓰나..? 싶은 생각이 들어 vector<int>& a 레퍼런스로 바꾸니 바로 통과...! 이럴 수가..!🤭

 

해결 코드

class Solution {
private:
	static bool compare(vector<int> a, vector<int> b) {
		return a[0] < b[0];
	}
public:
	int findMinArrowShots(vector< vector<int> >& points) {
		int end;
		int ans = 0;
		sort(points.begin(), points.end(), compare);

		for (int i = 0; i < points.size(); ++i) {
			if (ans == 0 || end < points[i][0]) {
				ans++;
				end = points[i][1];
			}
		}
		return ans;
	}
};