452. Minimum Number of Arrows to Burst Balloons / TypeScript

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].

 

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

 

 

풀이

function findMinArrowShots(points: number[][]): number {
    points.sort((a,b)=>a[0]-b[0])
    let res=1
    let [px,py]=points[0]
    for (let index = 1; index < points.length; index++) {
        const [x,y] = points[index];
        if(py>=x){
            px=Math.max(px,x)
            py=Math.min(py,y)
        }else{
            [px,py]=[x,y]
            res++
        }
    }
    return res
};

 

함수는 평면에 있는 여러 개의 풍선들이 주어졌을 때, 최소한의 화살로 모든 풍선을 터뜨릴 수 있는 횟수를 구하는 문제

 

 

예시 풀이

입력: [[10,16],[2,8],[1,6],[7,12]]

points.sort((a, b) => a[0] - b[0]);

 

• 풍선의 시작점을 기준으로 오름차순 정렬

 

1. 시작점 기준으로 정렬 후: [[1,6],[2,8],[7,12],[10,16]]

 

let res = 1;
let [px, py] = points[0];

 

 

• res는 필요한 화살의 개수입니다. 처음에는 1로 시작합니다. 왜냐하면 적어도 한 개의 화살은 필요하기 때문입니다.
• [px, py]는 현재 화살이 터뜨릴 수 있는 풍선의 범위를 나타냅니다. 초기값은 첫 번째 풍선의 시작점과 끝점으로 설정

for (let index = 1; index < points.length; index++) {
  const [x, y] = points[index];

 

 

 

• 풍선 리스트를 순회하는 반복문. 두 번째 풍선부터 비교를 시작
• [x, y]는 현재 풍선의 시작점(x)과 끝점(y)을 나타냄

if (py >= x) {
  px = Math.max(px, x);
  py = Math.min(py, y);
}

 

 

 

• 현재 화살이 닿을 수 있는 범위 [px, py]가 현재 풍선의 시작점(x)과 겹치는지 확인
• py >= x라면, 현재 화살은 다음 풍선과 겹침. 즉, 하나의 화살로 두 풍선을 모두 터뜨릴 수 있음
• 이 경우:
  • px는 두 풍선의 시작점 중 큰 값으로 갱신. 이는 화살이 닿는 구간의 시작점을 업데이트.
  • py는 두 풍선의 끝점 중 작은 값으로 갱신. 이는 화살이 닿는 구간의 끝점을 업데이트.

else {
  [px, py] = [x, y];
  res++;
}

 

 

• 현재 화살이 다음 풍선과 겹치지 않는다면 (py < x), 새로운 화살이 필요
• 이때, 새로운 화살을 쏘는 범위를 현재 풍선의 범위 [x, y]로 갱신하고, 화살 개수를 1 증가

 

예시 실행 과정

입력: [[10,16],[2,8],[1,6],[7,12]]

1. 정렬: [[1,6],[2,8],[7,12],[10,16]]
2. 초기화: res = 1, [px, py] = [1, 6]
3. 반복문 실행:
   • 두 번째 풍선 [2, 8]: 겹침 (6 >= 2), px = 2, py = 6
   • 세 번째 풍선 [7, 12]: 겹치지 않음 (6 < 7), 새로운 화살 추가, res = 2, px = 7, py = 12
   • 네 번째 풍선 [10, 16]: 겹침 (12 >= 10), px = 10, py = 12
4. 결과 반환: res = 2