3604. Minimum Time to Reach Destination in Directed Graph Medium

1/**
2 * [3604] Minimum Time to Reach Destination in Directed Graph
3 *
4 * You are given an integer n and a directed graph with n nodes labeled from 0 to n - 1. This is represented by a 2D array edges, where edges[i] = [ui, vi, starti, endi] indicates an edge from node ui to vi that can only be used at any integer time t such that starti <= t <= endi.
5 * You start at node 0 at time 0.
6 * In one unit of time, you can either:
7 * 
8 * 	Wait at your current node without moving, or
9 * 	Travel along an outgoing edge from your current node if the current time t satisfies starti <= t <= endi.
10 * 
11 * Return the minimum time required to reach node n - 1. If it is impossible, return -1.
12 *  
13 * <strong class="example">Example 1:
14 * <div class="example-block">
15 * Input: <span class="example-io">n = 3, edges = [[0,1,0,1],[1,2,2,5]]</span>
16 * Output: <span class="example-io">3</span>
17 * Explanation:
18 * <img src="https://assets.leetcode.com/uploads/2025/06/05/screenshot-2025-06-06-at-004535.png" style="width: 150px; height: 141px;" />
19 * The optimal path is:
20 * 
21 * 	At time t = 0, take the edge (0 &rarr; 1) which is available from 0 to 1. You arrive at node 1 at time t = 1, then wait until t = 2.
22 * 	At time t = 2, take the edge (1 &rarr; 2) which is available from 2 to 5. You arrive at node 2 at time 3.
23 * 
24 * Hence, the minimum time to reach node 2 is 3.
25 * </div>
26 * <strong class="example">Example 2:
27 * <div class="example-block">
28 * Input: <span class="example-io">n = 4, edges = [[0,1,0,3],[1,3,7,8],[0,2,1,5],[2,3,4,7]]</span>
29 * Output: <span class="example-io">5</span>
30 * Explanation:
31 * <img src="https://assets.leetcode.com/uploads/2025/06/05/screenshot-2025-06-06-at-004757.png" style="width: 170px; height: 219px;" />
32 * The optimal path is:
33 * 
34 * 	Wait at node 0 until time t = 1, then take the edge (0 &rarr; 2) which is available from 1 to 5. You arrive at node 2 at t = 2.
35 * 	Wait at node 2 until time t = 4, then take the edge (2 &rarr; 3) which is available from 4 to 7. You arrive at node 3 at t = 5.
36 * 
37 * Hence, the minimum time to reach node 3 is 5.
38 * </div>
39 * <strong class="example">Example 3:
40 * <div class="example-block">
41 * Input: <span class="example-io">n = 3, edges = [[1,0,1,3],[1,2,3,5]]</span>
42 * Output: <span class="example-io">-1</span>
43 * Explanation:
44 * <img src="https://assets.leetcode.com/uploads/2025/06/05/screenshot-2025-06-06-at-004914.png" style="width: 150px; height: 145px;" />
45 * 
46 * 	Since there is no outgoing edge from node 0, it is impossible to reach node 2. Hence, the output is -1.
47 * </div>
48 *  
49 * Constraints:
50 * 
51 * 	1 <= n <= 10^5
52 * 	0 <= edges.length <= 10^5
53 * 	edges[i] == [ui, vi, starti, endi]
54 * 	0 <= ui, vi <= n - 1
55 * 	ui != vi
56 * 	0 <= starti <= endi <= 10^9
57 * 
58 */
59pub struct Solution {}
60
61// problem: https://leetcode.com/problems/minimum-time-to-reach-destination-in-directed-graph/
62// discuss: https://leetcode.com/problems/minimum-time-to-reach-destination-in-directed-graph/discuss/?currentPage=1&orderBy=most_votes&query=
63
64// submission codes start here
65
66impl Solution {
67    pub fn min_time(n: i32, edges: Vec<Vec<i32>>) -> i32 {
68        0
69    }
70}
71
72// submission codes end
73
74#[cfg(test)]
75mod tests {
76    use super::*;
77
78    #[test]
79    fn test_3604() {
80    }
81}
82