Marathon Recovery Circuit

Minimum initial value for a feasible order of requirement-change pairs

MediumGreedySortingExchange Argument

After a marathon, a runner must complete every activity in a recovery village. The activities can be completed in any order, exactly once each.

You are given stations, where stations[i] = [required, change] describes one activity:

  • The runner must have at least required stamina immediately before starting it.
  • Completing it changes the runner's stamina by change. A positive change restores stamina, while a negative change consumes stamina.

Stamina has no upper limit. There is no travel cost between activities, and stamina changes only when an activity is completed. Every activity satisfies required + change >= 0, so completing an activity after meeting its requirement cannot make stamina negative.

Return the smallest nonnegative integer starting stamina that allows the runner to complete every activity in some order. If there are no activities, return 0.

Examples

Example 1

Input: stations = [[7,-5],[4,3],[9,-2]]
Output: 6

The restoring activity can be completed before either draining activity. Among the draining activities, doing the one with the larger required post-activity reserve first avoids an unnecessarily high starting requirement.

Example 2

Input: stations = [[5,4],[2,1]]
Output: 4

Although the second activity restores more stamina, its entry requirement is higher. Completing the lower-requirement restoring activity first makes the other activity easier to enter.

Example 3

Input: stations = []
Output: 0

No activities need to be completed, so no starting stamina is needed.

Constraints

  • 0 <= stations.length <= 2400
  • Each element of stations contains exactly two integers: [required, change].
  • 0 <= required <= 100000
  • -100000 <= change <= 100000
  • required + change >= 0 for every activity

The intended solution uses a greedy exchange argument followed by sorting. Its time complexity is O(n log n), and its auxiliary space complexity is O(n).

Hints

Show hint 1

Consider swapping two adjacent activities. Can a stamina-restoring activity always be moved before a stamina-draining activity without increasing the necessary starting stamina?

Show hint 2

For two draining activities, compare required + change. After choosing an order, track the cumulative stamina change and the starting stamina needed to meet each entry requirement.

Follow-up questions

What an interviewer might ask once you have a working solution.

  • How would you return an optimal activity order, breaking all sorting ties by original index?
  • If stamina had a fixed upper capacity and excess restoration were discarded, which parts of the ordering argument would need to be reconsidered?

Practice this with an AI interviewer

Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.

Start this problem