@zzg_zzm For your last question, I think the answer depends on how the input is given. If it is given in two separate array, we can in-place sort both arrays at the same time. Then, we don't bother with the O(N) space for encapsulation, and we can reduce the space complexity to O(k). However, the time complexity is bounded by sorting. So, when k is much less than N, I'd like to use your solution.
You first do the first project and increase your capital to 12. Now you have enough capital to do second project. When you do that You increase your capital to 14 and now you have enough capital to do last project and you can increase your capital to 17. It is similar to example.
@slcott Well while I do know how to fix it, I wanted to see how your actual code did it. Because with the usual way, which is also what your posted code suggested, I doubt it got 266 ms. I also know a way to make it that fast, but that's different from what you made yours look like, and it's an optimization I'd find worth sharing. I was hoping you'd do that.
Edit: Hmm, I just tried it again. I thought when I tested it yesterday, your solution fixed the normal way (imports above the class) got times around 500 ms. But now I do get times around 250-300ms. I thought yesterday I only got there by importing inside your function, making them fast local variables instead of slower global ones. But now that doesn't seem to make a noticeable difference, and now that I think about that, I don't think it should, as it's not that significant in comparison to the rest of the code. Oh well... in any case, I think it would've been better had you posted your full code. Then I wouldn't have had to make assumptions, and people who don't know how to make it work could still easily play with it.