Show problems as
Classic problem #452MediumArrayGreedySorting

Minimum Number of Arrows to Burst Balloons

Real-world version: Fewest Inspection Mileposts
Tracked in this browser only
Read Minimum Number of Arrows to Burst Balloons on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A rail operator has to sign off a list of track segments. The i-th entry of points gives that segment as a pair [start_i, end_i], meaning the segment covers every milepost from start_i to end_i with both ends included.

An inspection is booked at one integer milepost x. Booking it signs off every segment that covers x, so a segment is signed off when start_i <= x <= end_i. Any milepost may be chosen and any number of inspections may be booked.

Return the smallest number of inspections that signs off every segment on the list.

Examples

Example 1

Input
points = [[9, 12], [1, 3], [4, 8], [2, 5]]
Output
3

Booking mileposts 3, 8 and 12 signs off all four segments: milepost 3 covers [1, 3] and [2, 5], milepost 8 covers [4, 8], and milepost 12 covers [9, 12]. No pair of mileposts reaches all four.

Example 2

Input
points = [[1, 2], [2, 3]]
Output
1

Both segments cover milepost 2, since the ends of a segment are included, so a single booking there signs off both.

Example 3

Input
points = [[1, 10], [2, 3], [4, 5]]
Output
2

Booking milepost 3 signs off [1, 10] and [2, 3], and booking milepost 5 signs off [4, 5]. A single booking cannot cover both [2, 3] and [4, 5], which share no milepost.

Constraints

  • 1 <= points.length <= 10^5
  • points[i].length == 2
  • -2^31 <= start_i < end_i <= 2^31 - 1

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def find_min_arrow_shots(points: list[list[int]]) -> int:
Java
public int findMinArrowShots(int[][] points)

More on the same topics