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.

Hint: Build cumulative endpoints

Each city owns tickets after the previous cumulative population through its own cumulative population; binary search finds the first endpoint at least as large as a ticket.

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.

Select Cities from Weighted Tickets

Given unique city names, positive population weights, and deterministic ticket numbers, return the city selected by each ticket. In the given city order, city i owns the next contiguous block of tickets whose length is populations[i]. Ticket numbers are one-indexed from 1 through the total population. Tickets may be empty, unsorted, or repeated, and the result must preserve their order.

Hints

1. Build cumulative population endpoints in the given city order.
2. For each ticket, find the first cumulative endpoint that is at least that ticket.

Approach

Build a cumulative endpoint for every city. Endpoint i is the last ticket owned by city i, so the endpoints are strictly increasing because all populations are positive. For each ticket, binary-search for the first endpoint that is greater than or equal to it. All earlier endpoints are smaller than the ticket, while this endpoint closes the first range containing it; therefore its index is exactly the selected city's index. Processing tickets independently also preserves duplicates and their supplied order. Use 64-bit integer storage in Java and C++ and exact safe integers in JavaScript so totals near 2^53 - 1 remain exact.

• Time complexity: O(n + q log n), where n is the number of cities and q is the number of tickets
• Space complexity: O(n + q) including the returned list