Alternative to DP, a Short, Straightforward O(N^2) Greedy Solution in Python
Approach\n Describe your approach to solving the problem. \nThe best solution with a length of l is based on the best solution with the length of l-1 and an ite
# Approach\n<!-- Describe your approach to solving the problem. -->\nThe best solution with a length of `l` is based on the best solution with the length of `l-1` and an item that is not selected yet. \nThus, my solution builds the solution from length 1 to `n`, one by one. \nBased on the solution of `l-1`, my solution picks up the best item from the remaining set `r`. The criteria is easy that the addition of the new item makes the lowest score. By exploring each of the items in `r` with an $O(1)$ scoring function, the overal complexity is $O(N^2)$.\n\n\n# Complexity\n- Time complexity: $O(N^2)$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $O(N)$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:\n        def cost(q, r, l):\n            return sum((l-i-1) * b for i, (_, b) in enumerate(q)) \\\n                   + sum(a + l * b for a, b in r)\n        q, r = [], sorted([(a, b) for a, b in zip(nums1, nums2)], key=lambda x: (x[1], x[0]))\n        if cost(q, r, len(q)) <= x:\n            return 0\n        while r:\n            prefix_sums = list(accumulate((b for _, b in q), initial=0))\n            best_score, best_i, best_j = -inf, -1, -1\n            j = 0\n            for i, (a2, b2) in enumerate(r):\n                while j < len(q) and q[j][1] < b2:\n                    j += 1\n                if (score := a2 + b2 * (j+1) - prefix_sums[j]) > best_score:\n                    best_score, best_i, best_j = score, i, j\n            q.insert(best_j, r.pop(best_i))\n            if cost(q, r, len(q)) <= x:\n                return len(q)\n        return -1\n```
['Greedy', 'Python3']