Find Minimum Log Transportation Cost

Difficulty: Easy | Acceptance: 42.30% | Paid: No Topics: Math

You are given an integer n and an array logs where logs[i] is the weight of the i-th log. You have a truck that can carry at most k logs at a time. The cost of a trip is the maximum weight of the logs in that trip. Return the minimum total cost to transport all logs.

• Examples
• Constraints
• Greedy with Sorting

Examples

Example 1

Input:

n = 6, m = 5, k = 5

Output:

5

Explanation: Cut the log with length 6 into logs with length 1 and 5, at a cost equal to 1 * 5 == 5. Now the three logs of length 1, 5, and 5 can fit in one truck each.

Example 2

Input:

n = 4, m = 4, k = 6

Output:

0

Explanation: The two logs can fit in the trucks already, hence we don’t need to cut the logs.

Constraints

1 <= n <= 10^5
1 <= logs[i] <= 10^9
1 <= k <= n

Greedy with Sorting

Intuition To minimize the total cost, we should minimize the sum of the maximum weights of each trip. The heaviest log will always incur a cost equal to its weight because it must be transported. To prevent other heavy logs from incurring high costs in separate trips, we should pair the heaviest logs together. This way, the lighter logs in the group “ride for free” (they don’t increase the trip cost). By sorting the logs in descending order and grouping them sequentially, we ensure that every k-th log (starting from the first) is the only one contributing to the total cost.

Steps

• Sort the logs array in descending order.
• Initialize total_cost to 0.
• Iterate through the sorted array with a step of k (i.e., indices 0, k, 2k, …).
• Add the value of the log at each of these indices to total_cost.
• Return total_cost.

class Solution:
    def minCost(self, logs: list[int], k: int) -> int:
        logs.sort(reverse=True)
        total_cost = 0
        for i in range(0, len(logs), k):
            total_cost += logs[i]
        return total_cost

Complexity

• Time: O(n log n) due to the sorting step. The iteration takes O(n).
• Space: O(1) or O(n) depending on the sorting algorithm’s space complexity (e.g., heapsort uses O(1), quicksort uses O(log n) stack space, Timsort uses O(n)).
• Notes: Sorting is the most efficient and standard approach for this problem given the constraints.