Formatted question description: https://leetcode.ca/all/815.html
815. Bus Routes
Level
Hard
Description
We have a list of bus routes. Each routes[i]
is a bus route that the i-th bus repeats forever. For example if routes[0] = [1, 5, 7]
, this means that the first bus (0-th indexed) travels in the sequence 1->5->7->1->5->7->1->… forever.
We start at bus stop S
(initially not on a bus), and we want to go to bus stop T
. Travelling by buses only, what is the least number of buses we must take to reach our destination? Return -1 if it is not possible.
Example:
Input:
routes = [[1, 2, 7], [3, 6, 7]]
S = 1
T = 6
Output: 2
Explanation:
The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.
Note:
- 1 <= routes.length <= 500`.
- 1 <= routes[i].length <= 500`.
- 0 <= routes[i][j] < 10 ^ 6`.
Solution
Use breadth first search. Use a map to store each route and the routes that have intersection with the route (which means the two routes have at least one common stop). Use a set to store the visited routes and use another set to store the routes that can reach T
. Starting from the routes that contain S
, find the routes that have intersection with the current route, until a route that can reach T
is met.
class Solution {
public int numBusesToDestination(int[][] routes, int S, int T) {
if (S == T)
return 0;
Map<Integer, Set<Integer>> map = new HashMap<Integer, Set<Integer>>();
int length = routes.length;
for (int i = 0; i < length; i++)
Arrays.sort(routes[i]);
Set<Integer> visitedSet = new HashSet<Integer>();
Set<Integer> targetRoutes = new HashSet<Integer>();
Queue<int[]> queue = new LinkedList<int[]>();
for (int i = 0; i < length; i++) {
for (int j = i + 1; j < length; j++) {
if (intersect(routes[i], routes[j])) {
Set<Integer> set1 = map.getOrDefault(i, new HashSet<Integer>());
Set<Integer> set2 = map.getOrDefault(j, new HashSet<Integer>());
set1.add(j);
set2.add(i);
map.put(i, set1);
map.put(j, set2);
}
}
}
for (int i = 0; i < length; i++) {
int indexS = binarySearch(routes[i], S);
if (indexS >= 0) {
visitedSet.add(i);
queue.offer(new int[]{i, 0});
}
int indexT = binarySearch(routes[i], T);
if (indexT >= 0)
targetRoutes.add(i);
}
while (!queue.isEmpty()) {
int[] routeDepth = queue.poll();
int routeIndex = routeDepth[0];
int depth = routeDepth[1] + 1;
if (targetRoutes.contains(routeIndex))
return depth;
Set<Integer> nextRoutes = map.getOrDefault(routeIndex, new HashSet<Integer>());
for (int nextRoute : nextRoutes) {
if (visitedSet.add(nextRoute))
queue.offer(new int[]{nextRoute, depth});
}
}
return -1;
}
public boolean intersect(int[] route1, int[] route2) {
int index1 = 0, index2 = 0;
int length1 = route1.length, length2 = route2.length;
while (index1 < length1 && index2 < length2) {
if (route1[index1] == route2[index2])
return true;
else if (route1[index1] < route2[index2])
index1++;
else
index2++;
}
return false;
}
public int binarySearch(int[] array, int target) {
int low = 0, high = array.length - 1;
while (low <= high) {
int mid = (high - low) / 2 + low;
int num = array[mid];
if (num == target)
return mid;
else if (num > target)
high = mid - 1;
else
low = mid + 1;
}
return -low - 1;
}
}