Very Simple (Greedy) Java Solution using two PriorityQueues


  • 36

    The idea is each time we find a project with max profit and within current capital capability.
    Algorithm:

    1. Create (capital, profit) pairs and put them into PriorityQueue pqCap. This PriorityQueue sort by capital increasingly.
    2. Keep polling pairs from pqCap until the project out of current capital capability. Put them into
      PriorityQueue pqPro which sort by profit decreasingly.
    3. Poll one from pqPro, it's guaranteed to be the project with max profit and within current capital capability. Add the profit to capital W.
    4. Repeat step 2 and 3 till finish k steps or no suitable project (pqPro.isEmpty()).

    Time Complexity: For worst case, each project will be inserted and polled from both PriorityQueues once, so the overall runtime complexity should be O(NlgN), N is number of projects.

    public class Solution {
        public int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) {
            PriorityQueue<int[]> pqCap = new PriorityQueue<>((a, b) -> (a[0] - b[0]));
            PriorityQueue<int[]> pqPro  = new PriorityQueue<>((a, b) -> (b[1] - a[1]));
            
            for (int i = 0; i < Profits.length; i++) {
                pqCap.add(new int[] {Capital[i], Profits[i]});
            }
            
            for (int i = 0; i < k; i++) {
                while (!pqCap.isEmpty() && pqCap.peek()[0] <= W) {
                    pqPro.add(pqCap.poll());
                }
                
                if (pqPro.isEmpty()) break;
                
                W += pqPro.poll()[1];
            }
            
            return W;
        }
    }
    

  • 0
    S

    @shawngao brilliant solution


  • 0

    Brilliant solution! : )


  • 1

    Really awesome. Make it a little bit more OO:

    public class Solution {
        public int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) {
            PriorityQueue<Point> q1 = new PriorityQueue<>((a, b) -> (a.cap - b.cap));
            PriorityQueue<Point> q2 = new PriorityQueue<>((a, b) -> (b.pro - a.pro));
            for(int i = 0; i<Profits.length; i++){
                q1.add(new Point(Profits[i], Capital[i]));
            }
            for(int i = 0; i<k; i++){
                while(!q1.isEmpty() && q1.peek().cap<=W) q2.add(q1.poll());
                if(q2.size()==0) break;
                W += q2.poll().pro;
            }
            return W;
        }
        class Point{
            int pro; 
            int cap;
            public Point(int p, int c){
                this.pro = p;
                this.cap = c;
            }
        }
    }
    

    Select all you can select (<=W) from pqCap and add to pqPro. All in pqPro are valid selections! Then select the best one from pqPro.


  • 0
    K

    I tried this approach using C++, but it doesn't pass the last test with 50000 items

    class Solution {
    public:
        struct CompLess {
            bool operator() (const pair<int, int>& l, const pair<int, int>& r) {
                return l.first > r.first;
            }    
        };
        
        struct CompGreater {
            bool operator() (const pair<int, int>& l, const pair<int, int>& r) {
                return l.second < r.second;
            }    
        };
        
        int findMaximizedCapital(int k, int W, vector<int>& Profits, vector<int>& Capital) {
            priority_queue< pair<int, int>, vector< pair<int, int> >,  CompLess> qcap;
            for (int i = 0; i < Profits.size(); ++i) {
                qcap.push( make_pair(Capital[i], Profits[i]) );
            }
            
            priority_queue< pair<int, int>, vector< pair<int, int> >,  CompGreater> qprof;
            for (int i = 0; i < k; ++i) {
                while (!qcap.empty() && qcap.top().first <= W) {
                    qprof.push(qcap.top());
                    qcap.pop();
                }
                
                if (qprof.empty())
                    break;
                
                W += qprof.top().second;
                qprof.pop();
            }
            return W;
        }
    };
    

  • 0
    S

    A very clean and elegant solution


  • 1

    Same idea, 41ms

    public class Solution {
        public int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) {
            if (Profits == null || Profits.length == 0) return 0;
            int n = Profits.length;
            PriorityQueue<Tuple> q = new PriorityQueue();
            for (int i = 0; i < n; i++) {
                q.add(new Tuple(Profits[i], Capital[i]));
            }
            while (!q.isEmpty() && k-- > 0) {
                Queue<Tuple> tmp = new ArrayDeque();
                while (!q.isEmpty() && q.peek().cap > W) tmp.add(q.poll());
                if (q.isEmpty()) return W;
                Tuple cur = q.poll();
                W += cur.pro;
                while (!tmp.isEmpty()) q.add(tmp.poll());
            }
            return W;
        }
        
        class Tuple implements Comparable<Tuple> {
            int pro, cap;
            public Tuple(int pro, int cap) {
                this.pro = pro;
                this.cap = cap;
            }
            
            public int compareTo(Tuple that) {
                return that.pro - this.pro;
            }
        }
    }
    

  • 0
    S

    How do you guys come up with such elegant solutions. Is it all based upon numerous hours of practice or more than that?


  • 0

    @saiha

    Practice makes perfect


  • 0
    X

    @KirillLykov I met the same problem. Have you solved it yet?


  • 0
    K

    @xieexiaotuzi nope, I'm passively waiting for someone proposing an alternative. There is also a solution using multimap but it cannot be faster than using two queues (right?).


  • 0
    X

    @KirillLykov I don't know exactly why multi_map is slower than prority_queue. I think the time complexity is the same. So I need someone's help.


  • 0
    K

    @xieexiaotuzi the complexity asymptotically is the same, but the constants are different. I guess red-black tree is used for multimap implementation, so it should have a greater constant. For this problem, I first wrote O(N2) solution, it passes all the tests except this N=50000. I wonder what is the referee solution for this problem.


  • 0

    @KirillLykov Try submitting it again, now that debug mode has been turned off.


  • 0
    K

    @StefanPochmann thank you, it works.


  • 1

    AC C++ version. 50-60ms

    struct CapCmp {
        bool operator()(pair<int, int> &a, pair<int, int> &b) {
            return a.first > b.first;
        }
    };
    struct ProCmp {
        bool operator()(pair<int, int> &a, pair<int, int> &b) {
            return a.second < b.second;
        }
    };
    class Solution {
    public:
        int findMaximizedCapital(int k, int W, vector<int>& Profits, vector<int>& Capital) {
            priority_queue<pair<int, int>, vector<pair<int, int>>, CapCmp> cap;
            priority_queue<pair<int, int>, vector<pair<int, int>>, ProCmp> pro;
            for (int i = 0; i < Profits.size(); ++i) cap.push({ Capital[i], Profits[i] });
            while (k--) {
                while (cap.size() && cap.top().first <= W) {
                    pro.push(cap.top());
                    cap.pop();
                }
                if (pro.empty()) return W;
                W += pro.top().second;
                pro.pop();
            }
            return W;
        }
    };
    

  • 3

    Great solution. I think there are two possible improvements:

    • Space: it seems that pqPro doesn't need to store the capital components since it is never used.
    • Time: Since we only have maximum k projects to do even though there are N total projects available, I think the time factor logN might be cut down to log(min(N,k)) by maintaining a maximum capped size of priority queue. Imagine when N is huge compared with k, adding all projects to priority queues might be unnecessary. I think this is similar to the classic "get largest k elements " problem, but need to be careful when a project can be discarded.

  • 0
    M

    great solution with two PriorityQueue.
    I think the time-complexity is O( k * N * logN ) ?
    N is the input size.


  • 0

    @mycoy said in Very Simple (Greedy) Java Solution using two PriorityQueues:

    great solution with two PriorityQueue.
    I think the time-complexity is O( k * N * logN ) ?
    N is the input size.

    The estimate of O(k N logN) is too conservative. The fact is that the algorithm must finish when either k projects are done or all doable projects have been worked, so the factor k is only implicit. The time complexity is actually O(N logN) because each project at most goes through both priority queues once for each.

    Actually, I think it might optimize the time with a factor of log(min(N,k)) instead of logN because we don't have to keep more than k elements in the queue. But I need to work out the details. (Considering when N is huge compared with k)


  • -3
    P

    why cannot I create the priorityqueue same way as you did? My Eclipse just won't compile the code below:

    (a, b) -> (a[0] - b[0])
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.