LintCode: Big Business

Big Business

Similar Problems:

Given two arrays a and b. a[i] stands for the royalties of the film i, b[i] represents the money that the movie i can sell, now we have principal k, find how much money can be earned in the end.(Each movie only needs to be bought once and can only be sold once.)


  • All the input does not exceed 100000
  • The size of array does not exceed 10000.


Given a = [3,1,5], b = [4,3,100], k = 1,return 4.

Buy the second video first, then sell it, buy the first video, sell it again, and finally the principal becomes 4.
Given a = [3,1,5], b = [4,3,100], k = 10,return 108.

Buy all the videos, sell them, and finally the principal becomes 108.


Credits To:

Leave me comments, if you have better ways to solve.

## Blog link:
class Solution:
    @param a: The cost of the film
    @param b: The price of the selling of the film
    @param k: The principal
    @return: The answer
    def bigBusiness(self, a, b, k):
        ## Basic Ideas: sort a
        ##    From left to right, stop when we can't afford it
        ##    Note: there might be movie which might lose money 
        ## Complexity: Time O(n*log(n)), Space O(n)
        res = k
        c = list(zip(a, b))
        for (royalty, earn) in c:
            if royalty > res: break
            if earn > royalty:
                res += earn - royalty
        return res

Share It, If You Like It.

Leave a Reply

Your email address will not be published.