452. Minimum Number of Arrows to Burst Balloons

Problem

Bài toán yêu cầu tìm số mũi tên tối thiểu cần bắn để làm nổ tất cả các quả bóng, với quả bóng là một đoạn [x_start, x_end] trên trục hoành. Một mũi tên bắn lên tại vị trí x sẽ làm nổ tất cả các bóng mà x nằm trong đoạn [x_start, x_end] của bóng đó

Example

x_start <= x <= x_end

typescripttypescript

1|---| : bóng 1 (1,6)
2      |-----| : bóng 2 (2,8)
3            |------| : bóng 4 (7,12)
4                  |------| : bóng 3 (10,16)

Bạn có thể bắn một mũi tên tại x = 6 (nổ bóng 1 và 2)

Bắn thêm một mũi tên tại x = 12 (nổ bóng 4 và 3)

Approach

Nếu nhiều quả bóng có đoạn giao nhau, ta chỉ cần một mũi tên bắn vào vùng giao nhau đó để làm nổ tất cả các bóng chồng lấp

Do đó, bài toán chuyển thành tìm số lượng các nhóm đoạn giao nhau (interval groups)

Cách làm

Sắp xếp các quả bóng theo tọa độ x_end tăng dần

Duyệt qua từng quả bóng

Nếu x_start của bóng hiện tại lớn hơn x_end của bóng cuối cùng đã bắn, cần một mũi tên mới

Nếu không, bóng này đã được bắn bởi mũi tên trước đó

💡

Mỗi lần gặp một bóng không giao với vùng đã bắn, ta tăng số mũi tên lên một và cập nhật vùng bắn mới

Time and space complexity

TC: O(nlogn)

SC: O(n)

Solution

typescripttypescript

1function findMinArrowShots(points: number[][]): number {
2    if(points.length === 0) return 0;
3    points.sort((a, b) => a[1] - b[1]);
4    
5    let arrows = 1;
6    let end = points[0][1];
7    for(let i =1 ; i < points.length; i++) {
8	    if(points[i][0] > end) {
9		    arrows++;
10		    end = points[i][1];
11	    }
12    }
13    return arrows;
14};

💡

Giải thích

Sắp xếp các đoạn theo điểm kết thúc

Khởi tạo arrows = 1, end là điểm kết thúc của bóng đầu tiên

Duyệt từng bóng, nếu bóng tiếp theo bắt đầu sau end thì cần mũi tên mới, cập nhật lại end

💡

Tại sao initial arrows = 1?

Biến arrows thường được khởi tạo là 1 (hoặc tăng lên 1 khi gặp bóng đầu tiên) vì

Ngay khi bắt đầu duyệt qua các quả bóng (đã được sắp xếp theo điểm kết thúc), ta cần ít nhất một mũi tên để bắn quả bóng đầu tiên

Nếu chỉ có một quả bóng, chắc chắn phải cần một mũi tên để làm nổ nó

Sau đó, mỗi khi gặp một quả bóng không giao với vùng đã bắn trước đó, ta mới tăng arrows lên thêm 1 cho mũi tên mới

Loading content...

1function findMinArrowShots(points: number[][]): number { 2 if(points.length === 0) return 0; 3 points.sort((a, b) => a[1] - b[1]); 4 5 let arrows = 1; 6 let end = points[0][1]; 7 for(let i =1 ; i < points.length; i++) { 8 if(points[i][0] > end) { 9 arrows++; 10 end = points[i][1]; 11 } 12 } 13 return arrows; 14};

452. Minimum Number of Arrows to Burst Balloons

Related Posts

Related Posts

452. Minimum Number of Arrows to Burst Balloons

Related Posts

2. Add Two Numbers

3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

4. Median of Two Sorted Arrays

5. Longest Palindromic Substring

6. Zigzag Conversion

9. Palindrome Number

11. Container With Most Water

12. Integer to Roman

13. Roman to Integer

14. Longest Common Prefix

17. Letter Combinations of a Phone Number

19. Remove Nth Node From End of List

20. Valid Parentheses

21. Merge Two Sorted Lists

Related Posts

2. Add Two Numbers

3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

4. Median of Two Sorted Arrays

5. Longest Palindromic Substring

6. Zigzag Conversion

9. Palindrome Number

11. Container With Most Water

12. Integer to Roman

13. Roman to Integer

14. Longest Common Prefix

17. Letter Combinations of a Phone Number

19. Remove Nth Node From End of List

20. Valid Parentheses

21. Merge Two Sorted Lists