0606MediumArrayGreedySorting

Fewest Inspection Mileposts

Tracked in this browser only

Trains the technique from

LeetCode 452Minimum Number of Arrows to Burst Balloons

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def find_min_arrow_shots(points: list[list[int]]) -> int:

Java

public int findMinArrowShots(int[][] points)

The intended approach

Time O(n log n): the sort dominates and the sweep is linear.Space O(n) for the sorted copy of the segment list.

Sort the segments by their finishing milepost and sweep through them, keeping the milepost of the most recent booking. A segment whose start lies at or before that milepost is already signed off and can be skipped. Otherwise a new booking is needed, and placing it at this segment's finishing milepost is safe because among the segments still unsigned this one finishes first, so no other segment that this booking could reach is lost by moving the booking that far right.

Pythonentry point: find_min_arrow_shots

def find_min_arrow_shots(points):
    # O(n log n) time from the sort, O(n) space for the sorted copy.
    # Order the segments by where they finish. Walking that order, the segment
    # that finishes first among the ones still uncleared has to be cleared by
    # some milepost, and booking that milepost at its finishing post clears at
    # least as much as any earlier choice would.
    ordered = sorted(points, key=lambda seg: seg[1])
    visits = 0
    booked = None
    for start, end in ordered:
        if booked is None or start > booked:
            visits += 1
            booked = end
    return visits

The obvious version

Only the finishing mileposts of the segments need to be considered as booking sites, since any booking can be slid rightwards to the nearest finish among the segments it signs off without losing any of them. So try every set of finishing mileposts of size 1, then of size 2, and so on, and report the first size that signs off all the segments.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_find_min_arrow_shots(points):
    import itertools
    # Any set of mileposts can be slid rightwards until each one lands on the
    # finishing post of a segment it clears, so only those posts need trying.
    candidates = sorted({seg[1] for seg in points})
    for size in range(1, len(candidates) + 1):
        for combo in itertools.combinations(candidates, size):
            covered = True
            for start, end in points:
                hit = False
                for post in combo:
                    if start <= post <= end:
                        hit = True
                        break
                if not hit:
                    covered = False
                    break
            if covered:
                return size
    return len(points)

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in