Ежедневная часть (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.