Số mũi tên tối thiểu để làm nổ bóng bay trong C++

Cho các bóng bay hình cầu trên mặt phẳng 2D, mỗi bóng bay có tọa độ bắt đầu và kết thúc của đường kính ngang. Mũi tên bắn thẳng đứng từ trục x. Bóng bay tại [xstart, xend] nổ nếu mũi tên bắn tại x với xstart ≤ x ≤ xend. Tìm số mũi tên tối thiểu để làm nổ tất cả bóng bay. Ví dụ: [[10,16],[2,8],[1,6],[7,12]] → 2 (bắn tại x=6 nổ 2 bóng, x=11 nổ 2 bóng còn lại).

Giải thuật

• Sắp xếp các khoảng theo tọa độ kết thúc tăng dần.
• currEnd := end của khoảng đầu tiên, cnt := 1.
• Duyệt từ khoảng thứ 2: nếu currEnd < start của khoảng hiện tại thì cnt++, currEnd = end hiện tại.
• Trả về cnt.

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    static bool cmp(vector<int>& a, vector<int>& b) {
        return a[1] < b[1];
    }
    int findMinArrowShots(vector<vector<int>>& points) {
        sort(points.begin(), points.end(), cmp);
        int n = points.size();
        if (!n) return 0;
        int currEnd = points[0][1];
        int cnt = 1;
        for (int i = 1; i < n; i++) {
            if (currEnd < points[i][0]) {
                cnt++;
                currEnd = points[i][1];
            }
        }
        return cnt;
    }
};

Đầu vào

[[10,16],[2,8],[1,6],[7,12]]

Đầu ra

2