Ежедневная часть (e) C++ # 156, Распространенная проблема на собеседовании: автобусные маршруты
Сегодня мы рассмотрим распространенную проблему на собеседованиях: автобусные маршруты.
Учитывая список автобусных маршрутов, где route[i] = {b1,b2,b3} означает, что автобус i останавливается на остановках b1, b2 и b3, определите наименьшее количество автобусов, необходимых для достижения целевой автобусной остановки, начиная с исходной. .
Возвратите -1, если цель недостижима.
Прежде чем вы продолжите читать решение, я рекомендую вам попробовать решить его самостоятельно. Вот ссылка на Compiler Explorer с парой тестов: https://compiler-explorer.com/z/ThToveWP8.
Решение
Мы могли бы решить эту проблему, выполнив простой поиск в ширину по автобусным остановкам; однако у нас есть две проблемы. Во-первых, у нас нет удобного способа определить, до каких автобусных остановок мы можем добраться. И хотя мы могли бы построить структуру данных для этого, наша вторая проблема немного более фундаментальна. Поиск в ширину масштабируется с количеством ребер в графе; поэтому, если мы будем работать с автобусами, которые останавливаются на многих остановках, количество состояний будет быстро расти.
Поэтому давайте думать об автобусах, а не об автобусных остановках. Нам понадобится структура данных для сопоставления «соединений», то есть шин, которые мы можем изменить на каждой строке. Однако, как только он у нас появится, наш поиск в ширину будет масштабироваться в зависимости от количества автобусных линий.
Чтобы построить нашу структуру данных о соединениях, мы можем отсортировать каждую линию и найти пересечения между каждыми двумя линиями шины. Это потребует O(s*log(s)) для сортировки, а затем O(b*b*s) для построения (где s — количество остановок, а b — количество автобусов).
Поиск в ширину займет O(b*b) (b узлов, каждый с ребрами b-1).
// There is no convenient is_overlapping algorithm unfortunately bool overlaps(const std::vector<int>& left, const std::vector<int>& right) { ptrdiff_t i = 0; ptrdiff_t j = 0; while (i < std::ssize(left) && j < std::ssize(right)) { while (i < std::ssize(left) && left[i] < right[j]) ++i; while (i < std::ssize(left) && j < std::ssize(right) && left[i] > right[j]) ++j; if (i < std::ssize(left) && j < std::ssize(right) && left[i] == right[j]) return true; } return false; } int min_tickets(std::vector<std::vector<int>> routes, int source, int target) { if (source == target) { return 0; } // Map of bus -> connecting busses std::vector<std::vector<int>> connections(routes.size()); for (auto &route : routes) std::ranges::sort(route); // Flag for whether a bus stops at target std::vector<bool> is_dest(routes.size(), false); // Flag for whether this bus was already visited std::vector<bool> visited(routes.size(), false); // Queue for BFS std::queue<std::pair<int,int>> q; for (ptrdiff_t i = 0; i < std::ssize(routes); ++i) { // The bus stops at source, one of our starting buses if (std::ranges::binary_search(routes[i], source)) { q.push({i,1}); visited[i] = true; } // The bus stops at target if (std::ranges::binary_search(routes[i], target)) is_dest[i] = true; // Find all other busses that connect to this bus for (ptrdiff_t j = i+1; j < std::ssize(routes); ++j) { if (overlaps(routes[i],routes[j])) { connections[i].push_back(j); connections[j].push_back(i); } } } // BFS while (!q.empty()) { auto [current,len] = q.front(); q.pop(); if (is_dest[current]) return len; for (auto bus : connections[current]) { if (visited[bus]) continue; q.push({bus, len+1}); visited[bus] = true; } } return -1; }
Откройте решение в Compiler Explorer.