Problem statement

A directed graph has n nodes numbered 0 to n - 1. Each edges[i] = [ui, vi, starti, endi] is a directed edge from ui to vi that can only be used at an integer time t with starti <= t <= endi; using it takes exactly one unit of time, so leaving ui at time t means arriving at vi at time t + 1.

You are at node 0 at time 0. At any node you may wait for any amount of time.

Return the minimum time at which you can arrive at node n - 1, or -1 if it cannot be reached.

Example 1

Input: n = 3, edges = [[0,1,0,1],[1,2,2,5]]
Output: 3
Explanation: Leave 0 at time 0 and reach 1 at time 1, wait until 2, then reach 2 at time 3.

Example 2

Input: n = 4, edges = [[0,1,0,3],[1,3,7,8],[0,2,1,5],[2,3,4,7]]
Output: 5
Explanation: Waiting at 0 until time 1, going to 2 (time 2), waiting until 4 and taking the last edge arrives at 5; the route through 1 cannot arrive before 8.

Example 3

Input: n = 3, edges = [[1,0,1,3],[1,2,3,5]]
Output: -1
Explanation: No edge leaves node 0.

Constraints

• 1 <= n <= 10^5
• 0 <= edges.length <= 10^5
• edges[i] == [ui, vi, starti, endi]
• 0 <= ui, vi <= n - 1
• ui != vi
• 0 <= starti <= endi <= 10^9

Hints for Minimum Time to Reach Destination in Directed Graph

1. Hint 1

   Arriving at a node earlier is never worse: you can always wait. So each node only needs its earliest arrival time.

2. Hint 2

   From a node reached at time t, an edge with window [start, end] is usable only if t <= end, and then it delivers you at max(t, start) + 1.

3. Hint 3

   That transition is monotone in t, so Dijkstra on arrival times works: pop the earliest node, relax its usable edges.

How to solve Minimum Time to Reach Destination in Directed Graph

Earliest-arrival search with time windows: because waiting is free, a later arrival can never open an option an earlier one lacks, so Dijkstra's greedy order is safe.

Approach

1. Build adjacency lists of (v, start, end) per node.
2. Set time[0] = 0 and push node 0 onto a min-heap keyed by time.
3. Pop the node u with the smallest time t (skip stale entries); if it is n - 1, return t.
4. For each edge with t <= end, relax v with max(t, start) + 1.
5. If the heap empties, return -1.

Why it works

For a fixed edge the arrival max(t, start) + 1 is non-decreasing in the departure time t, and the set of usable edges only shrinks as t grows. Hence an earlier arrival at u dominates a later one, which is the property Dijkstra's exchange argument needs.

Complexity

• Time — O((n + E) log E)
• Space — O(n + E)

Pitfalls

• An edge whose window has closed (t > end) is unusable even though you could have waited before it — you cannot go back in time.
• With n = 1 you are already at the destination: the answer is 0.
• Times reach about 10^9, so a packed heap key needs 64 bits.

Reference solution

Python

from typing import List
import heapq

def minTime(n: int, edges: List[List[int]]) -> int:
    adj = [[] for _ in range(n)]
    for u, v, s, e in edges:
        adj[u].append((v, s, e))
    INF = float("inf")
    dist = [INF] * n
    dist[0] = 0
    heap = [(0, 0)]
    while heap:
        t, u = heapq.heappop(heap)
        if t > dist[u]:
            continue
        if u == n - 1:
            return t
        for v, s, e in adj[u]:
            if t <= e:
                nt = max(t, s) + 1
                if nt < dist[v]:
                    dist[v] = nt
                    heapq.heappush(heap, (nt, v))
    return -1

Java

public static int minTime(int n, int[][] edges) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int k = 0; k < edges.length; k++) adj.get(edges[k][0]).add(k);
    final long SH = 131072L;
    long[] dist = new long[n];
    Arrays.fill(dist, Long.MAX_VALUE);
    dist[0] = 0;
    PriorityQueue<Long> heap = new PriorityQueue<>();
    heap.add(0L);
    while (!heap.isEmpty()) {
        long key = heap.poll();
        int u = (int) (key % SH);
        long t = key / SH;
        if (t > dist[u]) continue;
        if (u == n - 1) return (int) t;
        for (int k : adj.get(u)) {
            int[] ed = edges[k];
            if (t > ed[3]) continue;
            long nt = Math.max(t, (long) ed[2]) + 1;
            if (nt < dist[ed[1]]) { dist[ed[1]] = nt; heap.add(nt * SH + ed[1]); }
        }
    }
    return -1;
}

C++

int minTime(int n, vector<vector<int>>& edges) {
    vector<vector<int>> adj(n);
    for (int k = 0; k < (int) edges.size(); k++) adj[edges[k][0]].push_back(k);
    vector<long long> dist(n, LLONG_MAX);
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> heap;
    dist[0] = 0;
    heap.push(make_pair(0LL, 0));
    while (!heap.empty()) {
        long long t = heap.top().first;
        int u = heap.top().second;
        heap.pop();
        if (t > dist[u]) continue;
        if (u == n - 1) return (int) t;
        for (int k : adj[u]) {
            vector<int>& ed = edges[k];
            if (t > ed[3]) continue;
            long long nt = max(t, (long long) ed[2]) + 1;
            if (nt < dist[ed[1]]) { dist[ed[1]] = nt; heap.push(make_pair(nt, ed[1])); }
        }
    }
    return -1;
}

JavaScript

var minTime = function(n, edges) {
    var adj = [], dist = [], SH = 131072;
    for (var i = 0; i < n; i++) { adj.push([]); dist.push(Infinity); }
    for (var k = 0; k < edges.length; k++) adj[edges[k][0]].push(k);
    dist[0] = 0;
    var heap = [0];
    while (heap.length > 0) {
        var key = heapPop(heap);
        var u = key % SH, t = (key - u) / SH;
        if (t > dist[u]) continue;
        if (u === n - 1) return t;
        for (var j = 0; j < adj[u].length; j++) {
            var ed = edges[adj[u][j]];
            if (t > ed[3]) continue;
            var nt = Math.max(t, ed[2]) + 1, v = ed[1];
            if (nt < dist[v]) { dist[v] = nt; heapPush(heap, nt * SH + v); }
        }
    }
    return -1;
};

var heapPush = function(h, v) {
    h.push(v);
    var i = h.length - 1;
    while (i > 0) {
        var p = (i - 1) >> 1;
        if (h[p] <= h[i]) break;
        var t = h[p]; h[p] = h[i]; h[i] = t;
        i = p;
    }
};

var heapPop = function(h) {
    var top = h[0];
    var last = h.pop();
    if (h.length > 0) {
        h[0] = last;
        var j = 0;
        for (;;) {
            var l = 2 * j + 1, r = l + 1, s = j;
            if (l < h.length && h[l] < h[s]) s = l;
            if (r < h.length && h[r] < h[s]) s = r;
            if (s === j) break;
            var t = h[s]; h[s] = h[j]; h[j] = t;
            j = s;
        }
    }
    return top;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More graph problems

• Minimize Maximum Component Cost Medium
• Minimum Time for K Connected Components Medium
• Power Grid Maintenance Medium
• Unit Conversion I Medium
• Digit Operations to Make Two Integers Equal Medium
• Find Minimum Time to Reach Last Room II Medium