# code tpl

{%hackmd theme-dark %}

city A city B [10:00, 14:00]

city B city D [14:00, 16:00]

city K to city P
city A to city D
A -> B (14:00) -> B (14:00) -> D(16:00)

A -> B (10, 14)
A -> C (9, 12)

B->D (13, 15)
C->X (12, 13)
C->D (11, 15)
X->D (14, 18)

A -> B, C
B -> D
C -> X, D

B, C => minHeap(X)
X: 13

Situation

Task

Action

Result

// trains: [[0, 1, 10, 14], [0, 2, 9, 15], [1, 2, 14, 18]], [cityA, cityB, depart, arrive]
// V citys
// E schedules
// TC: O(V + ElogV)  VlogE
bool arrive(vector<vector<int>> &schedules, int src, int dst)
{
    // [0, 1, 10, 14], [0, 2, 9, 12], [1, 3, 13, 15], [2, 9, 12, 13], [9, 3, 14, 18]
    // src: 0, dst: 3
    // construct graph
    unordered_map<int, vector<vector<int>>> graph; // src city: [depart, arrive, next]
    for (auto &schedule: schedules) {
        int startStation = schedule[0];
        int nextStation = schedule[1];
        int departTime = schedule[2];
        int arriveTime = schedule[3];
        graph[start].push_back({departTime, arriveTime, nextStation});
    }
    // 0: [10, 14, 1], [9, 12, 2]
    // 1: [13, 15, 3]
    // 2: [12, 13, 9]
    // 9: [14, 18, 3]
    
    // [depart time, arrive time, next station]
    priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> minHeap;
    minHeap.push({0,0, src}); // [[0, 0, 0]]

    while (!minHeap.empty()) {
        int departTime = minHeap.top()[0]; // 10
        int arriveTime = minHeap.top()[1]; // 14
        int station = minHeap.top()[2]; // 1
        minHeap.pop(); //[[10, 14, 1]]
        if (station == dst) { // 2 != 3
            return true;
        }

        for (auto &schedule: graph[station]) { //[13, 15, 3]
            int depart = schedule[0]; // 13
            int arrive = schedule[1]; // 15
            int nextStation = schedule[2];// 3
            if (depart >= arriveTime) { 
                minHeap.push({depart, arrive, nextStation});
                // [[12, 13, 9]]
            }
            
        }
    }
    
    return false;
    // run Dijkstra's Algorithms - alog
}
M: 

node i : -1
root x
x|i i-1(i-1)|y
x|j j-2(j-2)|y
x|
x|
-1|
###### tags: `mock interview` `面試`