Find Maximum Eastbound City Visits and Parse CSV

Eastbound City Route Planner

You are given a string csv_data representing city coordinates and metadata in CSV format. Your goal is to parse the CSV records and determine the longest valid itinerary of cities where each consecutive city is strictly to the east (greater longitude) of the previous one. If there is a tie in latitude or longitude constraints, or multiple routes of the same maximum length, return the lexicographically smallest itinerary (by city name).

Input Format

csv_data contains one or more lines separated by newline (\n). The first line is always a header: "city_name,latitude,longitude".

Each subsequent line represents a city record. Note that fields may follow standard CSV quoting rules:

• A field may be enclosed in double quotes "...".
• If a field is quoted, it may contain commas , which must not be treated as delimiters.
• If a field is quoted, an escaped double quote is represented by two consecutive double quotes "".
• Unquoted fields will not contain commas or double quotes.

Constraints on the Route

1. A route is an ordered list of city names: [c_1, c_2, ..., c_k].
2. For every i from 1 to k - 1, longitude(c_{i+1}) > longitude(c_i).
3. In addition, northbound progress must not be reversed too sharply: latitude(c_{i+1}) >= latitude(c_i).
4. If multiple routes achieve the maximum number of visits k, choose the route that is lexicographically smallest when compared as lists of city names (e.g., ["A", "C"] is smaller than ["B", "A"]).

Interface

def max_eastbound_route(csv_data: str) -> list[str]:
    pass

Examples

Example 1:

csv_data = """city_name,latitude,longitude
"Denver, CO",39.7392,-104.9903
"Omaha, NE",41.2565,-95.9345
"Chicago, IL",41.8781,-87.6298
"St. Louis, MO",38.6270,-90.1994"""

max_eastbound_route(csv_data)
# Output: ["Denver, CO", "Omaha, NE", "Chicago, IL"]

Explanation: Longitudes are Denver (-104.99) = lat. St. Louis has lat 38.63, so Omaha -> St. Louis is invalid (38.6270 < 41.2565). The longest valid sequence has length 3: ["Denver, CO", "Omaha, NE", "Chicago, IL"].

Example 2:

csv_data = """city_name,latitude,longitude
"City ""A""",10.0,20.0
City B,15.0,20.0"""

max_eastbound_route(csv_data)
# Output: ["City \"A\""]

Explanation: Longitudes are equal (20.0), so no eastbound step can be taken between them. Both single-city routes have length 1. "City \"A\"" is lexicographically smaller than "City B".

Constraints

• Number of cities N: 1 <= N <= 1,000
• -90.0 <= latitude <= 90.0
• -180.0 <= longitude <= 180.0
• City names contain printable ASCII characters and are at most 100 characters long.
• Time complexity target: O(N^2) or better.