Minimum Cost to Cut a Stick
Given a wooden stick of length n units. The stick is labelled from 0 to n.
Given an integer array cuts where cuts[i] denotes a position where you should perform a cut.
You should perform all the cuts, and you can change the order of the cuts as you wish.
The cost of one cut is the length of the stick being cut. The total cost is the sum of the costs of all cuts. When you cut a stick, it is split into two smaller sticks, and the sum of their lengths is the length of the stick before the cut.
Return the minimum total cost of the cuts.
Example 1
Input
n = 7, cuts = [1,3,4,5]Output
16Rearranging the cuts to
[3, 5, 1, 4] gives total cost 7 + 4 + 3 + 2 = 16, which is minimum.Example 2
Input
n = 9, cuts = [5,6,1,4,2]Output
22The order
[4, 6, 5, 2, 1] has total cost 22, which is the minimum possible.Constraints
- 2 <= n <= 10^6
- 1 <= cuts.length <= min(n - 1, 100)
- 1 <= cuts[i] <= n - 1
- All the integers in
cutsarray are distinct.
Asked at 8 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.