Map Random Tickets to Population-Weighted Cities

Problem

Cities have positive population weights. Convert deterministic random tickets into city selections so that drawing a uniformly random ticket from 1 through total population would select each city in proportion to its population. Return the city selected for every supplied ticket.

Function Contract

Implement select_cities(cities, populations, tickets) -> list[str]. City i owns a contiguous ticket range of length populations[i] in the given city order.

Constraints

• 1 <= len(cities) = len(populations) <= 200000, and city names are unique.
• 1 <= populations[i] <= 10^12.
• sum(populations) <= 9007199254740991, which is 2^53 - 1.
• Every ticket is an integer in [1, sum(populations)].
• 0 <= len(tickets) <= 200000.
• All numeric inputs are within the exact cross-language integer range from -(2^53 - 1) through 2^53 - 1.

Examples

• Cities ["A","B","C"], populations [2,3,1], and tickets [1,2,3,5,6] return ["A","A","B","B","C"].
• With one city, every valid ticket selects that city.

Edge Cases

• The total may approach 2^53 - 1 but never exceed it.
• A ticket exactly on a cumulative boundary belongs to that boundary's city.
• Tickets can be unsorted and repeated.