Problem statement

https://leetcode.com/problems/minimum-initial-energy-to-finish-tasks/

Solution

Here we have very big number of possible ways in which order we can take our tasks, so we need to think about greedy approach. Imagine, that we have two tasks with $T_1 = (a_1, m_1)$ and $T_2 = (a_2, m_2)$. Let us consider two different ways, in which we can take these tasks:

  1. $T_1$, then $T_2$, then to fulfill both of them we need ammount $A$, such that: $A \geqslant m_1$ and $A - a_1 \geqslant m_2$ or we can rewrite it as $A \geqslant \max(m_1, m_2 + a_1)$.
  2. $T_2$, then $T_1$, then we have $A \geqslant \max (m_2, m_1 + a_2)$.

Imagine now, that $m_1 - a_1 \geqslant m_2 - a_2$.

  1. For $T_1 \to T_2$ we have $m_2 + a_1 \leqslant m_1 + a_2$, so $\max(m_1, m_2 + a_1) \leqslant m_1 + a_2$
  2. For $T_2 \to T_1$ we have $m_2 \leqslant m_1+a_2-a_1$, so $\max (m_2, m_1 + a_2) = m_1 + a_2$

It means that it is always worth to take the first order. So, we can swap all pairs and have proof by bubble sort that we need to sort our tasks with key equal to decrease of $m_i - a_i$.

Finally, we can simulate our process, keeping energy and lowest is the maximum negative number we meet.

Complexity

Time complexity is O(n log n), space is O(n).

Code

class Solution:
    def minimumEffort(self, tasks):
        energy, lowest = 0, 0
        for a, m in sorted(tasks, key = lambda x: x[0] - x[1]):
            lowest = min(lowest, energy - m)
            energy -= a
            
        return -lowest