Merge Operations for Minimum Travel Time

Problem

You are given a straight road of length l km, an integer n, an integer k, and two integer arrays, position and time, each of length n.

The array position lists the positions (in km) of signs in strictly increasing order (with position[0] = 0 and position[n - 1] = l).

Each time[i] represents the time (in minutes) required to travel 1 km between position[i] and position[i + 1].

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:

• Update the sign at index i + 1 so that its time becomes time[i] + time[i + 1].
• Remove the sign at index i.

Return the minimum total travel time (in minutes) to travel from 0 to l after exactly k merges.

Examples

Example 1

Input: l = 10, n = 4, k = 1, position = [0,3,8,10], time = [5,8,3,6]
Output: 62
Explanation:
* 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`.
* After the merge: 
* `position` array: `[0, 8, 10]`
* `time` array: `[5, 11, 6]`
*   * Segment | Distance (km) | Time per km (min) | Segment Travel Time (min)  
---|---|---|---  
0 -> 8 | 8 | 5 | 8 × 5 = 40  
8 -> 10 | 2 | 11 | 2 × 11 = 22  
* Total Travel Time: `40 + 22 = 62`, which is the minimum possible time after exactly 1 merge.

Example 2

Input: l = 5, n = 5, k = 1, position = [0,1,2,3,5], time = [8,3,9,3,3]
Output: 34
Explanation:
* 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`.
* After the merge: 
* `position` array: `[0, 2, 3, 5]`
* `time` array: `[8, 12, 3, 3]`
*   * Segment | Distance (km) | Time per km (min) | Segment Travel Time (min)  
---|---|---|---  
0 -> 2 | 2 | 8 | 2 × 8 = 16  
2 -> 3 | 1 | 12 | 1 × 12 = 12  
3 -> 5 | 2 | 3 | 2 × 3 = 6  
* Total Travel Time: `16 + 12 + 6 = 34`**,** which is the minimum possible time after exactly 1 merge.

Constraints

• 1 <= l <= 10^5
• 2 <= n <= min(l + 1, 50)
• 0 <= k <= min(n - 2, 10)
• position.length == n
• position[0] = 0 and position[n - 1] = l
• position is sorted in strictly increasing order.
• time.length == n
• 1 <= time[i] <= 100​
• 1 <= sum(time) <= 100​​​​​​

Solution

Method 1 – Dynamic Programming with Prefix Sums

Intuition

To minimize the total travel time after exactly k merges, we need to optimally merge adjacent segments. This is similar to the classical "merge stones" or "matrix chain multiplication" problem, where merging costs are based on segment lengths and times. Dynamic programming with prefix sums helps efficiently compute the minimum cost for all possible merges.

Approach

1. Compute the segment lengths: length[i] = position[i+1] - position[i] for all i.
2. Use DP: dp[i][j] is the minimum travel time to merge segments from i to j.
3. For each possible number of merges, try all possible partitions and update the DP table.
4. Use prefix sums to quickly calculate the total time for a segment.
5. After exactly k merges, return the minimum total travel time.

Code

C++

class Solution {
public:
    int minTravelTime(int l, int n, int k, vector<int>& position, vector<int>& time) {
        vector<int> length(n);
        for (int i = 0; i < n - 1; ++i) length[i] = position[i + 1] - position[i];
        vector<vector<int>> dp(n, vector<int>(n, INT_MAX));
        for (int i = 0; i < n; ++i) dp[i][i] = length[i] * time[i];
        for (int merge = 1; merge <= k; ++merge) {
            for (int i = 0; i + merge < n; ++i) {
                int j = i + merge;
                for (int m = i; m < j; ++m) {
                    dp[i][j] = min(dp[i][j], dp[i][m] + dp[m + 1][j]);
                }
            }
        }
        return dp[0][n - 1];
    }
};

Go

func minTravelTime(l, n, k int, position, time []int) int {
    length := make([]int, n)
    for i := 0; i < n-1; i++ {
        length[i] = position[i+1] - position[i]
    }
    dp := make([][]int, n)
    for i := range dp {
        dp[i] = make([]int, n)
        for j := range dp[i] {
            dp[i][j] = 1 << 30
        }
    }
    for i := 0; i < n; i++ {
        dp[i][i] = length[i] * time[i]
    }
    for merge := 1; merge <= k; merge++ {
        for i := 0; i+merge < n; i++ {
            j := i + merge
            for m := i; m < j; m++ {
                if dp[i][j] > dp[i][m]+dp[m+1][j] {
                    dp[i][j] = dp[i][m] + dp[m+1][j]
                }
            }
        }
    }
    return dp[0][n-1]
}

Java

class Solution {
    public int minTravelTime(int l, int n, int k, int[] position, int[] time) {
        int[] length = new int[n];
        for (int i = 0; i < n - 1; i++) length[i] = position[i + 1] - position[i];
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) Arrays.fill(dp[i], Integer.MAX_VALUE);
        for (int i = 0; i < n; i++) dp[i][i] = length[i] * time[i];
        for (int merge = 1; merge <= k; merge++) {
            for (int i = 0; i + merge < n; i++) {
                int j = i + merge;
                for (int m = i; m < j; m++) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][m] + dp[m + 1][j]);
                }
            }
        }
        return dp[0][n - 1];
    }
}

Kotlin

class Solution {
    fun minTravelTime(l: Int, n: Int, k: Int, position: IntArray, time: IntArray): Int {
        val length = IntArray(n)
        for (i in 0 until n - 1) length[i] = position[i + 1] - position[i]
        val dp = Array(n) { IntArray(n) { Int.MAX_VALUE } }
        for (i in 0 until n) dp[i][i] = length[i] * time[i]
        for (merge in 1..k) {
            for (i in 0 until n - merge) {
                val j = i + merge
                for (m in i until j) {
                    dp[i][j] = minOf(dp[i][j], dp[i][m] + dp[m + 1][j])
                }
            }
        }
        return dp[0][n - 1]
    }
}

Python

def min_travel_time(l: int, n: int, k: int, position: list[int], time: list[int]) -> int:
    length = [position[i+1] - position[i] for i in range(n-1)] + [0]
    dp = [[float('inf')] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = length[i] * time[i]
    for merge in range(1, k+1):
        for i in range(n - merge):
            j = i + merge
            for m in range(i, j):
                dp[i][j] = min(dp[i][j], dp[i][m] + dp[m+1][j])
    return dp[0][n-1]

Rust

impl Solution {
    pub fn min_travel_time(l: i32, n: i32, k: i32, position: Vec<i32>, time: Vec<i32>) -> i32 {
        let mut length = vec![0; n as usize];
        for i in 0..(n - 1) as usize {
            length[i] = position[i + 1] - position[i];
        }
        let mut dp = vec![vec![i32::MAX; n as usize]; n as usize];
        for i in 0..n as usize {
            dp[i][i] = length[i] * time[i];
        }
        for merge in 1..=k as usize {
            for i in 0..(n as usize - merge) {
                let j = i + merge;
                for m in i..j {
                    dp[i][j] = dp[i][j].min(dp[i][m] + dp[m + 1][j]);
                }
            }
        }
        dp[0][n as usize - 1]
    }
}

TypeScript

class Solution {
    minTravelTime(l: number, n: number, k: number, position: number[], time: number[]): number {
        const length = Array(n).fill(0);
        for (let i = 0; i < n - 1; ++i) length[i] = position[i + 1] - position[i];
        const dp = Array.from({ length: n }, () => Array(n).fill(Infinity));
        for (let i = 0; i < n; ++i) dp[i][i] = length[i] * time[i];
        for (let merge = 1; merge <= k; ++merge) {
            for (let i = 0; i + merge < n; ++i) {
                const j = i + merge;
                for (let m = i; m < j; ++m) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][m] + dp[m + 1][j]);
                }
            }
        }
        return dp[0][n - 1];
    }
}

Complexity

• ⏰ Time complexity: O(n^3), due to three nested loops in DP.
• 🧺 Space complexity: O(n^2), for the DP table.