Minimum Darts to Pop Intervals (Medium) — Practice with Code Visualizer

Imagine a carnival game where floating targets are arranged along a horizontal track. Each target is represented by a one-dimensional segment defined by its starting position and ending position along the track. A dart can be thrown at any specific position along the track, and it travels perfectly vertically, popping any target whose segment includes that position.

More formally, you are given a 2D integer array intervals where intervals[i] = [starti, endi] represents a target spanning from position starti to position endi (inclusive). A dart thrown at position x pops all targets where starti ≤ x ≤ endi.

Your goal is to determine the minimum number of darts required to pop every single target. There is no limit on how many darts you can use, and each dart pops all targets along its vertical path.

This is fundamentally an interval coverage optimization problem: find the minimum number of points (dart positions) such that every interval contains at least one of the chosen points.

All targets can be popped with just 2 darts:

Throw a dart at position x = 6, which pops targets [2,8] and [1,6] since 6 lies within both intervals.
Throw a dart at position x = 11, which pops targets [10,16] and [7,12] since 11 lies within both intervals. Thus, the minimum number of darts required is 2.

No two targets share any overlapping positions. Each target forms a completely disjoint interval:

[1,2] and [3,4] are separated (gap between 2 and 3)
[3,4] and [5,6] are separated (gap between 4 and 5)
[5,6] and [7,8] are separated (gap between 6 and 7) Since no single dart position can pop multiple targets, we need exactly 4 darts—one for each target.

Adjacent targets share boundary positions, allowing efficient coverage:

A dart at x = 2 pops targets [1,2] and [2,3] (2 is the right boundary of the first and left boundary of the second).
A dart at x = 4 pops targets [3,4] and [4,5] (4 is the shared boundary). With strategic placement at shared boundaries, only 2 darts are needed to pop all 4 targets.