题目

思路

• 此题可以等价于“用箭射气球”，也等价于“区间选点”，还是贴着右边界的做法。
• 想象一下，如果前个区间有公共点，那么用一个箭就可以引爆所有气球，对于第个点而言，选择前个端点中任意一个当做“不相交的区间”都是可行的。所以，不相交的区间个数，等于“箭”的个数。
• 还是贴着右边界，可以用最少的箭。

  代码

  ```cpp

  include

  include

using namespace std;

const int N = 1e5 + 5;

bool cmp(pair a, pair b) { return a.second < b.second; }

int main() { pair nums[N]; int n = 0; cin >> n; for (int i = 0; i < n; i++) { cin >> nums[i].first >> nums[i].second; }

sort(nums, nums + n, cmp);
int cnt = 1, right = nums[0].second; 
for (int i = 1; i < n; ++i) {
    if (right < nums[i].first) {
        cnt++;
        right = nums[i].second;
    }
}
cout << cnt << endl;
return 0;

} ```