问题描述

有一些球形气球贴在一堵用 XY 平面表示的墙面上。

墙面上的气球记录在整数数组 points，其中 points[i] = [x_start, x_end] 表示水平直径在 x_start 和 x_end 之间的气球。

你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点射出完全垂直地射出。

在坐标 x 处射出一支箭前，若有一个气球的直径的开始和结束坐标为 [x_start, x_end]，且满足 x_start <= x <= x_end，则该气球会被引爆。

可以射出的弓箭的数量没有限制。

前一个箭射出后， 可以无限地前进。

给你一个数组 points，返回引爆所有气球所必须射出的最小弓箭数。

---

格式

输入

• 一个整数数组 points，其中 points[i] = [x_start, x_end]。

输出

• 一个整数，表示最小弓箭数。

---

样例

样例1

输入

4
10 16
2 8
1 6
7 12

输出

2

解释

• 在 x = 6 处射箭，击破 [2,8] 和 [1,6]。
• 在 x = 11 处射箭，击破 [10,16] 和 [7,12]。

---

样例2

输入

4
1 2
3 4
5 6
7 8

输出

4

解释

每个气球需要射出一支箭，总共需要 4 支箭。

---

样例3

输入

4
1 2
2 3
3 4
4 5

输出

2

解释

• 在 x = 2 处射箭，击破 [1,2] 和 [2,3]。
• 在 x = 4 处射箭，击破 [3,4] 和 [4,5]。

---

提示

• 1 <= points.length <= 10⁵
• points[i].length == 2
• -2³¹ <= x_start < x_end <= 2³¹ - 1

---