Next place to visit by distance

Problem You are given places, each with a distance from the current location. Support repeated lookups of "which place should be visited next" — each query returns the nearest place not yet visited and marks it visited.

Input / Output

• Input: list of (place, distance) pairs, then a sequence of next() queries.
• Output: for each query, the nearest unvisited place.

Constraints

• Up to 10^5 places and queries — per-query linear scans (O(n) each) are the naive baseline to beat.

Example

• places = [(A,5),(B,2),(C,9)] → next() = B, next() = A, next() = C.

Expected approach

• Min-heap keyed by distance: build in O(n), each next() is O(log n) pop. If all queries are known upfront, sorting once (O(n log n)) and iterating is equivalent. Discuss supporting dynamic inserts (new places between queries) — the heap handles them naturally, a pre-sorted array does not.