Given a set of intervals — each delivery's valid time window, each dart's reach along a fence line, each balloon's horizontal span — find the fewest points such that every interval contains at least one of them. One inspector visiting a handful of moments can certify every delivery window; one arrow fired straight down can pop every balloon it passes through. This is interval point cover: a different question from Activity Selection's "pick the most non-overlapping intervals" even though both start from the same kind of input and both are solved by sorting once and sweeping left to right.
The greedy idea: sort every interval by its end, then walk the list once. If the current interval already contains the most recently placed point, it's already covered — do nothing. Otherwise, place a new point exactly at this interval's end and remember it as the new most-recent point. That's the whole algorithm — no lookahead, no backtracking. This is the site's seventh entry filed under Greedy, and like Activity Selection, Fractional Knapsack, and Job Sequencing, it's exactly optimal on every input — provable by an exchange argument, not just observed to work well.
Type a list of start-end pairs (comma-separated), pick a placement rule, and press
Load, then Step or Run. Each row is one interval,
ordered by whichever rule is selected — a green bar means a new point was placed at that interval
(shown in the log), a soft-tan bar means the interval was already stabbed by an earlier point, and
the accent tick marks the most recent point at the moment this row is decided. At the end, every
interval is independently re-checked against the final point set — not just trusted from the
algorithm's own bookkeeping — and any interval the point set actually misses turns red.
timeline
The proof is an exchange argument, same skeleton as Activity Selection's but run on the
opposite end of the sort. Let I be the interval with the smallest end value,
e. Every valid point set must place some point p inside
I, so p ≤ e. Since e is the smallest end value of
any interval, every other interval J has end(J) ≥ e ≥ p;
if J contained p to begin with, then start(J) ≤ p ≤ e,
so e also lands inside J. Sliding p right to e
therefore never uncovers anything p was covering, and it newly covers I
itself — so some optimal solution can always be rearranged to include e. Once
e is fixed as a safe point, discard every interval it stabs and the remaining problem
has the identical shape, so the same argument reapplies to the next-smallest end among what's
left, and so on. Sorting by end and sweeping once is exactly this induction unrolled: the point
this algorithm places for each not-yet-covered interval is always that interval's own end, which
is always the smallest end still on the table when it's placed.
On the demo's own eight-interval default set, this rule places exactly 3 points —
4, 10, 14 — confirmed optimal by brute force (no 2-point
set stabs all eight). The two rules below don't reach that on the same data — see Pitfalls.
function intervalPointCover(intervals) {
// intervals: [{ start, end }]
const sorted = [...intervals].sort((a, b) => a.end - b.end);
const points = [];
let last = null;
for (const iv of sorted) {
if (last === null || iv.start > last) {
points.push(iv.end);
last = iv.end;
}
}
return points;
}Placing the point at each interval's start instead of its end is valid but suboptimal. Switch the demo's rule to sort by end, point at start on the unchanged default data: every interval still ends up covered (this variant never produces an invalid result), but it needs 5 points instead of 3 — a point at an interval's start can fail to reach later intervals that a point at its end would have caught, since the end is always the rightmost position still guaranteed to lie inside that interval. Checked beyond this one example, not just asserted: across 10,000 randomized trials (seeded for reproducibility, 2–11 intervals each, endpoints 0–19), this variant was suboptimal on 6,754 of them (67.5%), with one generated instance needing 8 points where the true optimum — and the correct rule — is 3.
Sorting by start instead of end can produce a point set that doesn't even cover every
interval. Switch the demo's rule to sort by start, point at end on the unchanged
default data: the point set shrinks to just 10 and 14, and three
intervals — [4,8], [3,7], [3,4] — end up genuinely uncovered
by either point, flagged red once the demo's independent end-of-run check runs. On this data, the
interval processed first by start order is [2,10] (nothing starts earlier), so a point
lands at its end, 10; every one of the three short intervals just named starts before
10 and gets waved through as "covered" by that same check, even though none of them actually
contains 10. A bare minimal version of the same mechanism makes it clearest: three intervals
[1,100], [2,3], [4,5]. Processed by start, [1,100] comes first with
nothing placed yet, so a point lands at its end, 100. [2,3] and
[4,5] are then checked only against "does this interval start after 100,"
which they don't, so both are marked covered — but 100 doesn't actually lie in either
one. Sorting by end never allows this: whichever interval is processed next always has an end at
least as large as the last point placed, so that comparison is safe. By start, an already-placed
point can be arbitrarily far to the right of an interval that hasn't been processed yet. Checked
beyond the hand-built example: across the same 10,000-trial randomized sweep, this variant produced
an invalid (non-covering) point set on 7,153 of them (71.5%).
Time: O(n log n), entirely the initial sort — the sweep that
follows is a single O(n) pass, one comparison per interval against the running last
point. Space: O(n) for the sorted copy and the returned point list
(or O(1) extra if only counting points, not returning them). This demo's brute-force
optimal-count check, shown purely for comparison, is O(2^d · n) over the
d distinct end values and capped at 12 intervals so it stays instant — nothing about
the greedy algorithm itself needs it.
See Choosing a Greedy Strategy for how this entry's proof compares against the site's other nine Greedy entries — short version: this is Tier 1, exact on every input, by the same "swap the extreme choice in, recurse on an identically shaped remainder" pattern as Activity Selection, run from the opposite end of the sort.