Stamina for All the Chores

Hard

You have a list of chores chores, where chores[i] = [cost, need]: doing the chore uses up cost units of stamina, but you can only start it if your current stamina is at least need. For example, with stamina 8 you cannot start the chore [4, 9], while with stamina 10 you can do it and have 6 left. Chores can be done in any order. Return the smallest starting stamina that lets you finish all of them.

Example 1

chores=[[3, 5], [4, 9], [1, 2]] → 9

Starting with 9, do the demanding chores first: [4, 9] leaves 5, [3, 5] leaves 2, [1, 2] leaves 1. With 8 there is no order that works, because [4, 9] can never be started.

Example 2

chores=[[5, 5], [2, 8]] → 8

Doing [5, 5] first means arriving at [2, 8] with 8, so the start would be 13. Doing [2, 8] first needs only max(8, 2 + 5) = 8.

Example 3

chores=[[6, 6]] → 6

Constraints

1 ≤ len(chores) ≤ 10⁵
1 ≤ cost ≤ need ≤ 10⁴

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array Sorting

Similar problems

Growing Capital Project by Project Hard Distinct Word Shorthands Hard Most Orders by Their Deadlines Hard Narrowest Range Touching Every List Hard Two Marks in Every Range Hard

Input

chores=[[3, 5], [4, 9], [1, 2]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 103 tests on the server, hidden ones included.