Minimum Total Cost of All Required Stick Cuts
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
### Problem
A stick spans 0..n. Every distinct position in cuts must be cut once,in an order you may choose. Cutting a current piece costs that piece's length and splits it into two pieces. Return the minimum total cost of completing every requested cut.
```cpp
class Solution {
public:
int minCost(int n, vector<int>& cuts);
};
```
### Examples
**Example 1:**
```text
Input: n = 6, cuts = [2,4]
Output: 10
Explanation: Either first cut costs6,and the remaining requested cut lies in a length4 piece,costing4 more.
```
**Example 2:**
```text
Input: n = 10, cuts = [7]
Output: 10
Explanation: The only cut splits the original length10 piece,so its cost is10.
```
### Constraints
- `2 <= n <= 1000000`.
- cuts has length 1 to min(n-1,100).
- Cut positions are distinct integers in `[1,n-1]`.
### Contract considerations
All required cuts are distinct and strictly inside the stick.
```hint Read the boundary condition
Complete every required cut and charge the length of the piece being cut. Input order does not prescribe the cutting order.
```
### Boundary reminders
All required cuts are distinct and strictly inside the stick.
Overview: Minimum Total Cost of All Required Stick Cuts. A stick spans0..n. Every distinct position in cuts must be cut once,in an order you may choose.
