3538. Merge Operations for Minimum Travel Time Hard
1/**
2 * [3538] Merge Operations for Minimum Travel Time
3 *
4 * <p data-end="452" data-start="24">You are given a straight road of length l km, an integer n, an integer k<strong data-end="83" data-start="78">, and two integer arrays, position and time, each of length n.
5 * <p data-end="452" data-start="24">The array position lists the positions (in km) of signs in strictly increasing order (with position[0] = 0 and position[n - 1] = l).
6 * <p data-end="452" data-start="24">Each time[i] represents the time (in minutes) required to travel 1 km between position[i] and position[i + 1].
7 * <p data-end="593" data-start="454">You must perform exactly k merge operations. In one merge, you can choose any two adjacent signs at indices i and i + 1 (with i > 0 and i + 1 < n) and:
8 * <ul data-end="701" data-start="595">
9 * <li data-end="624" data-start="595">Update the sign at index i + 1 so that its time becomes time[i] + time[i + 1].
10 * <li data-end="624" data-start="595">Remove the sign at index i.
11 *
12 * <p data-end="846" data-start="703">Return the minimum total travel time (in minutes) to travel from 0 to l after exactly k merges.
13 *
14 * <strong class="example">Example 1:
15 * <div class="example-block">
16 * Input: <span class="example-io">l = 10, n = 4, k = 1, position = [0,3,8,10], time = [5,8,3,6]</span>
17 * Output: <span class="example-io">62</span>
18 * Explanation:
19 *
20 * <li data-end="121" data-start="11">
21 * <p data-end="121" data-start="13">Merge the signs at indices 1 and 2. Remove the sign at index 1, and change the time at index 2 to 8 + 3 = 11.
22 *
23 * <li data-end="144" data-start="15">After the merge:
24 *
25 * <li data-end="214" data-start="145">position array: [0, 8, 10]
26 * <li data-end="214" data-start="145">time array: [5, 11, 6]
27 * <li data-end="214" data-start="145" style="opacity: 0">
28 *
29 *
30 * <li data-end="214" data-start="145">
31 * <table data-end="386" data-start="231" style="border: 1px solid black;">
32 * <thead data-end="269" data-start="231">
33 * <tr data-end="269" data-start="231">
34 * <th data-end="241" data-start="231" style="border: 1px solid black;">Segment</th>
35 * <th data-end="252" data-start="241" style="border: 1px solid black;">Distance (km)</th>
36 * <th data-end="260" data-start="252" style="border: 1px solid black;">Time per km (min)</th>
37 * <th data-end="269" data-start="260" style="border: 1px solid black;">Segment Travel Time (min)</th>
38 * </tr>
39 * </thead>
40 * <tbody data-end="386" data-start="309">
41 * <tr data-end="347" data-start="309">
42 * <td style="border: 1px solid black;">0 → 8</td>
43 * <td style="border: 1px solid black;">8</td>
44 * <td style="border: 1px solid black;">5</td>
45 * <td style="border: 1px solid black;">8 × 5 = 40</td>
46 * </tr>
47 * <tr data-end="386" data-start="348">
48 * <td style="border: 1px solid black;">8 → 10</td>
49 * <td style="border: 1px solid black;">2</td>
50 * <td style="border: 1px solid black;">11</td>
51 * <td style="border: 1px solid black;">2 × 11 = 22</td>
52 * </tr>
53 * </tbody>
54 * </table>
55 *
56 * <li data-end="214" data-start="145">Total Travel Time: 40 + 22 = 62, which is the minimum possible time after exactly 1 merge.
57 * </div>
58 * <strong class="example">Example 2:
59 * <div class="example-block">
60 * Input: <span class="example-io">l = 5, n = 5, k = 1, position = [0,1,2,3,5], time = [8,3,9,3,3]</span>
61 * Output: <span class="example-io">34</span>
62 * Explanation:
63 *
64 * <li data-end="567" data-start="438">Merge the signs at indices 1 and 2. Remove the sign at index 1, and change the time at index 2 to 3 + 9 = 12.
65 * <li data-end="755" data-start="568">After the merge:
66 *
67 * <li data-end="755" data-start="568">position array: [0, 2, 3, 5]
68 * <li data-end="755" data-start="568">time array: [8, 12, 3, 3]
69 * <li data-end="755" data-start="568" style="opacity: 0">
70 *
71 *
72 * <li data-end="755" data-start="568">
73 * <table data-end="966" data-start="772" style="border: 1px solid black;">
74 * <thead data-end="810" data-start="772">
75 * <tr data-end="810" data-start="772">
76 * <th data-end="782" data-start="772" style="border: 1px solid black;">Segment</th>
77 * <th data-end="793" data-start="782" style="border: 1px solid black;">Distance (km)</th>
78 * <th data-end="801" data-start="793" style="border: 1px solid black;">Time per km (min)</th>
79 * <th data-end="810" data-start="801" style="border: 1px solid black;">Segment Travel Time (min)</th>
80 * </tr>
81 * </thead>
82 * <tbody data-end="966" data-start="850">
83 * <tr data-end="888" data-start="850">
84 * <td style="border: 1px solid black;">0 → 2</td>
85 * <td style="border: 1px solid black;">2</td>
86 * <td style="border: 1px solid black;">8</td>
87 * <td style="border: 1px solid black;">2 × 8 = 16</td>
88 * </tr>
89 * <tr data-end="927" data-start="889">
90 * <td style="border: 1px solid black;">2 → 3</td>
91 * <td style="border: 1px solid black;">1</td>
92 * <td style="border: 1px solid black;">12</td>
93 * <td style="border: 1px solid black;">1 × 12 = 12</td>
94 * </tr>
95 * <tr data-end="966" data-start="928">
96 * <td style="border: 1px solid black;">3 → 5</td>
97 * <td style="border: 1px solid black;">2</td>
98 * <td style="border: 1px solid black;">3</td>
99 * <td style="border: 1px solid black;">2 × 3 = 6</td>
100 * </tr>
101 * </tbody>
102 * </table>
103 *
104 * <li data-end="755" data-start="568">Total Travel Time: 16 + 12 + 6 = 34, which is the minimum possible time after exactly 1 merge.
105 * </div>
106 *
107 * Constraints:
108 *
109 * <li data-end="35" data-start="15">1 <= l <= 10^5
110 * <li data-end="52" data-start="36">2 <= n <= min(l + 1, 50)
111 * <li data-end="81" data-start="53">0 <= k <= min(n - 2, 10)
112 * <li data-end="81" data-start="53">position.length == n
113 * <li data-end="81" data-start="53">position[0] = 0 and position[n - 1] = l
114 * <li data-end="200" data-start="80">position is sorted in strictly increasing order.
115 * <li data-end="81" data-start="53">time.length == n
116 * <li data-end="81" data-start="53">1 <= time[i] <= 100
117 * <li data-end="81" data-start="53">1 <= sum(time) <= 100
118 *
119 */
120pub struct Solution {}
121
122// problem: https://leetcode.com/problems/merge-operations-for-minimum-travel-time/
123// discuss: https://leetcode.com/problems/merge-operations-for-minimum-travel-time/discuss/?currentPage=1&orderBy=most_votes&query=
124
125// submission codes start here
126
127impl Solution {
128 pub fn min_travel_time(l: i32, n: i32, k: i32, position: Vec<i32>, time: Vec<i32>) -> i32 {
129 0
130 }
131}
132
133// submission codes end
134
135#[cfg(test)]
136mod tests {
137 use super::*;
138
139 #[test]
140 fn test_3538() {
141 }
142}
143Back
© 2026 bowen.ge All Rights Reserved.