Minimum cost to cut stick
You have a wooden stick of length n marked from 0 to n. You must perform all the cuts at the positions listed in cuts, in any order you choose. The cost of one cut equals the current length of the stick piece being cut, and after a cut the piece splits into two. Return the minimum total cost to perform every cut. Here 2 <= n <= 10^6 and cuts has at most 100 distinct positions strictly between 0 and n.
Implement
min_cost_cut_stick(n: int, cuts: list[int]) → intExamples
in
[7,[1,3,4,5]]out16What a strong answer looks like
State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.
0:00 of about 30 min
solution.py
InputExpectedGot
[7,[1,3,4,5]]16not run yetsample