To find an itinerary from a given list of tickets, you need
to reconstruct the journey based on the given pairs of departure and arrival
airports. Each ticket can be represented as a pair of strings, and the goal is
to use all the tickets to form an itinerary that uses each ticket exactly once.
One common problem-solving approach is to use a graph
traversal technique, where each ticket is an edge in the graph, and each
airport is a node.
Here’s how you can achieve this in Java:
- Model
the problem as a graph:
Ø
Each airport is a node.
Ø
Each ticket is a directed edge from one airport
to another.
- Use
a data structure to store the graph:
Ø
Use a Map<String,
PriorityQueue<String>> to represent the adjacency list of the graph.
The priority queue will help in automatically sorting the destinations to
ensure the lexicographically smallest itinerary when there are multiple
choices.
- Perform
Hierholzer’s algorithm to find the Eulerian path:
Ø
Hierholzer’s algorithm is typically used to find
an Eulerian path in a graph. An Eulerian path visits every edge exactly once.
Ø
Since this is a directed graph, you'll need to
start from a specific node (usually "JFK" in many standard problems).
Step-by-Step Solution
java
|
import java.util.*; public class ItineraryFinder { public static List<String>
findItinerary(List<List<String>> tickets) { // Graph
represented as adjacency list Map<String,
PriorityQueue<String>> flights = new HashMap<>();
List<String> result = new LinkedList<>(); // Build the
graph for
(List<String> ticket : tickets) {
flights.computeIfAbsent(ticket.get(0), k -> new
PriorityQueue<>()).add(ticket.get(1)); } // Start the
DFS from "JFK"
dfs("JFK", flights, result); // Since we add
destinations to result after visiting, we need to reverse the result
Collections.reverse(result); return result; } private static void dfs(String airport,
Map<String, PriorityQueue<String>> flights, List<String>
result) {
PriorityQueue<String> destinations = flights.get(airport); while
(destinations != null && !destinations.isEmpty()) {
dfs(destinations.poll(), flights, result); }
result.add(airport); } public static void main(String[] args)
{
List<List<String>> tickets = new ArrayList<>();
tickets.add(Arrays.asList("MUC", "LHR"));
tickets.add(Arrays.asList("JFK", "MUC"));
tickets.add(Arrays.asList("SFO", "SJC"));
tickets.add(Arrays.asList("LHR", "SFO"));
List<String> itinerary = findItinerary(tickets);
System.out.println(itinerary); // Output: [JFK, MUC, LHR, SFO, SJC] } } |
Explanation:
- Building
the Graph:
Ø
We use a HashMap where each key is a starting
airport and the value is a priority queue of destinations. This ensures that
when there are multiple destinations from an airport, we always visit the
lexicographically smallest one first.
- Depth-First
Search (DFS):
Ø
We start the DFS from "JFK".
Ø
For each airport, we recursively visit all its
destinations (by polling from the priority queue).
Ø
After visiting all the destinations from an
airport, we add the airport to the result list.
- Reversing
the Result:
Ø
Since we add an airport to the result list only
after all its destinations have been visited, the resulting list is in reverse
order of the required itinerary. Hence, we reverse the list at the end.
This approach ensures that all tickets are used exactly once
and the itinerary is lexicographically smallest when multiple options are
available.
Some other Approach To find an itinerary from a given
list of tickets using below example:
Java
Step 1
|
import java.util.ArrayList; import java.util.HashMap; import java.util.LinkedList; import java.util.List; import java.util.Map; /** * * @author Kartik Mandal * */ public class ItinearyTest {
/** * If it is sorted order data in
the list. * Find out source and
destination. * @return */ private static List<FlightInfo>
getFilteredFlightInfos(String originAirportCode, String
destinationAirportCode, List<FlightInfo> source) {
if (originAirportCode == null && destinationAirportCode == null) {
return source;
}
List<FlightInfo> filteredFlightInfos = new ArrayList<>();
boolean sourceFound = false;
boolean destinationFound = false;
for (FlightInfo flightInfo : source) {
if (!sourceFound) {
if (flightInfo.getOrigin().equals(originAirportCode)) {
sourceFound = true;
}
}
if (!destinationFound) {
if (flightInfo.getDestination()
.equals(destinationAirportCode)) {
destinationFound = true;
}
}
if (sourceFound || destinationFound) {
filteredFlightInfos.add(FlightInfo);
}
if (sourceFound && destinationFound) {
return filteredFlightInfos;
}
}
throw new RuntimeException("Error");
}
/**
* If it is unsorted data Create a HashMap of given pair of itinerary.
Find
* the starting point of itinerary. Create a reverse HashMap. Traverse
* 'travelItinerary'. For every key of dataset, check if it is there in
* 'reverseMap'. If a key is not present, then we found the starting
point.
* Now select the sub itinerary from and to of the range and put in
* linkedList. Match the filter data.
*
* @param originAirportCode
* @param destinationAirportCode
* @param selectOrigin
* @param travelItinerary
* @return
*/
private static boolean isAirportCodeMatched(String originAirportCode, String
destinationAirportCode, String selectOrigin, Map<String, String>
travelItinerary) { if
(originAirportCode == null && destinationAirportCode == null) {
return true; } Map<String,
String> reverseItineraryMap = new HashMap<String, String>(); for
(Map.Entry<String, String> entry : travelItinerary.entrySet())
reverseItineraryMap.put(entry.getValue(), entry.getKey()); String start =
null; for
(Map.Entry<String, String> entry : travelItinerary.entrySet()) {
if (!reverseItineraryMap.containsKey(entry.getKey()))
{
start = entry.getKey();
break;
} } if (start ==
null) {
return false; } String origin =
start; String
destination = travelItinerary.get(start);
List<String> list = new LinkedList<>(); boolean flag =
false; if
(start.equals(originAirportCode)) {
list.add(start);
while (destination != null)
{
if (destination.equals(destinationAirportCode))
{
flag = true;
break;
}
list.add(destination);
destination = travelItinerary.get(destination);
} } else {
destination = travelItinerary.get(start);
while (destination != null)
{
if (origin.equals(originAirportCode))
{
list.add(origin);
break;
}
origin = destination;
destination = travelItinerary.get(destination);
}
while (destination != null)
{
if (destination.equals(destinationAirportCode))
{
flag = true;
break;
}
list.add(destination);
destination = travelItinerary.get(destination);
} } if
(list.contains(originAirportCode) && flag) {
return list.contains(selectOrigin); } else {
return false; } }
public static void main(String[] args) {
System.out.println("==========================UnSorted List from sorce
to destination ======================");
Map<String, String> travelItinerary = new HashMap<String,
String>();
travelItinerary.put("MSP", "ORD");
travelItinerary.put("TXL", "JFK");
travelItinerary.put("ORD", "TXL");
travelItinerary.put("JFK", "BOM");
travelItinerary.put("BOM", "CCU");
System.out.println(isAirportCodeMatched("ORD", "CCU",
"JFK",
travelItinerary));
System.out
.println("==========================Sorted List from sorce to
destination ======================");
List<FlightInfoTO> list = new ArrayList<FlightInfoTO>();
FlightInfoTO f1 = new FlightInfoTO("MSP", "ORD");
FlightInfoTO f2 = new FlightInfoTO("ORD", "TXL");
FlightInfoTO f3 = new FlightInfoTO("TXL", "JFK");
FlightInfoTO f4 = new FlightInfoTO("JFK", "BOM");
FlightInfoTO f5 = new FlightInfoTO("BOM", "CCU");
list.add(f1);
list.add(f2);
list.add(f3);
list.add(f4);
list.add(f5);
List<FlightInfoTO> sss = getFilteredFlightInfos("ORD",
"CCU", list);
System.out.println(sss);
} } |
Step 2:
|
public class FlightInfo {
private String origin;
private String destination;
public FlightInfo(String origin, String destination) {
super();
this.origin = origin;
this.destination = destination;
}
public String getOrigin() {
return origin;
}
public void setOrigin(String origin) {
this.origin = origin;
}
public String getDestination() {
return destination;
}
public void setDestination(String destination) {
this.destination = destination;
}
@Override
public String toString() {
return "FlightInfo [origin=" + origin + ", destination="
+ destination + "]";
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result
+ ((destination == null) ? 0 : destination.hashCode());
result = prime * result + ((origin == null) ? 0 : origin.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
FlightInfo other = (FlightInfo) obj;
if (destination == null) {
if (other.destination != null)
return false;
} else if (!destination.equals(other.destination))
return false;
if (origin == null) {
if (other.origin != null)
return false;
} else if (!origin.equals(other.origin))
return false;
return true;
} } |
Given a list of tickets, find itinerary in order using
the given list.
Example:
|
Input: "Chennai"
-> "Banglore" "Bombay"
-> "Delhi" "Goa" -> "Chennai" "Delhi" -> "Goa" Output: Bombay->Delhi,
Delhi->Goa, Goa->Chennai, Chennai->Banglore, |
 |
| Itinerary from a given list of tickets |
0 Comments