Reconstruct Itinerary
HardGreedySorting
Description
Given a list of airline tickets as pairs [from, to], reconstruct the itinerary in order. The itinerary must begin with 'JFK'. If multiple valid itineraries exist, return the one with the smallest lexical order.
Examples
Input:
tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]Output:
["JFK","MUC","LHR","SFO","SJC"]Explanation:
Valid path starting from JFK.
Input:
tickets = [["JFK","SFO"]]Output:
["JFK","SFO"]Explanation:
With a single ticket from JFK to SFO, the itinerary starts at JFK and then uses that ticket to reach SFO.
Input:
tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]Output:
["JFK","ATL","JFK","SFO","ATL","SFO"]Explanation:
This example demonstrates handling multiple tickets from the same departure city. From JFK, destinations ATL and SFO are available. Since ATL < SFO lexicographically, ATL is chosen first, following the greedy approach of picking the smallest destination at each step.
Constraints
- •
1 ≤ tickets.length ≤ 300 - •
tickets[i].length == 2