600. Starting Energy
A delivery robot has a list of jobs, where tasks[i] = [cost, gate]. To start job i the robot's battery must hold at least gate units of energy, and finishing the job then drains exactly cost units. A job's cost may be larger than its gate, and the battery level is allowed to dip below zero after a job; only the level at the moment a job starts is checked.
The robot must complete every job exactly once, in any order you choose. Return the smallest starting battery level that lets it finish all jobs without ever being below a job's gate when that job begins. Remaining energy after all jobs does not matter. Aim for O(n log n) time and O(n) space.
Example 1
- Input:
- tasks = [[2,4],[3,3]]
- Output:
- 5
- Explanation:
Doing [2,4] first and [3,3] second needs max(4, 2+3) = 5, while the reverse order needs max(3, 3+4) = 7, so the answer is 5.
Example 2
- Input:
- tasks = [[1,2],[2,4],[4,8]]
- Output:
- 8
- Explanation:
The best order is [4,8], [2,4], [1,2], which needs max(8, 4+4, 6+2) = 8.
Example 3
- Input:
- tasks = [[5,5]]
- Output:
- 5
- Explanation:
A single job needs at least its gate, which is 5.
Constraints
1 ≤ tasks.length ≤ 100000tasks[i].length == 21 ≤ tasks[i][0], tasks[i][1] ≤ 10000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 3,600 msC++ 900 msJava 1,800 msJavaScript 1,800 msTypeScript 1,800 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)