Sort Weighted Points
MediumGreedy · Amazon
There are n points on a number line. Point i starts at position i and has weight weights[i]. All weights are distinct.
In one operation you choose a point i and move it exactly distances[i] units to the right. Points only ever move right, each point always jumps by its own distance, and any point may be moved any number of times. Points may pass over each other while moving.
Return the minimum number of operations needed so that, reading the final positions from left to right, the weights are strictly increasing. In other words, the lightest point must end strictly to the left of the second lightest, which must end strictly to the left of the third lightest, and so on. Two points may not finish at the same position.
Example 1
- Input:
- weights = [3, 6, 5, 2], distances = [4, 3, 2, 1]
- Output:
- 5
- Explanation
- In weight order the points are the 2 (at 3), the 3 (at 0), the 5 (at 2) and the 6 (at 1). The 2 stays put. The 3 jumps once to 4. The 5 must pass 4, so it jumps twice (2 to 4 to 6). The 6 must pass 6, so it jumps twice (1 to 4 to 7). That is 1 + 2 + 2 = 5.
Example 2
- Input:
- weights = [4, 1, 3, 2], distances = [1, 2, 3, 4]
- Output:
- 7
- Explanation
- The lightest point (weight 1) stays at 1. Weight 2 is at 3, already to its right. Weight 3 is at 2 and must pass 3: one jump of 3 takes it to 5. Weight 4 is at 0 with distance 1 and must pass 5, so it needs 6 jumps. The total is 0 + 0 + 1 + 6 = 7.
Example 3
- Input:
- weights = [2, 1], distances = [5, 1]
- Output:
- 1
- Explanation
- The weight-1 point is at 1, so the weight-2 point at 0 must move past it. A single jump of 5 takes it to 5, which is enough.
Constraints
1 <= weights.length == distances.length <= 10^51 <= weights[i] <= 10^9, and all weights are distinct1 <= distances[i] <= 10^9