Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

502. IPO

Time: $O(n\log n)$

Space: $O(n)$

			


struct T {
  int pro;
  int cap;
  T(int pro, int cap) : pro(pro), cap(cap) {}
};

class Solution {
 public:
  int findMaximizedCapital(int k, int W, vector<int>& Profits,
                           vector<int>& Capital) {
    auto compareC = [](const T& a, const T& b) { return a.cap > b.cap; };
    auto compareP = [](const T& a, const T& b) { return a.pro < b.pro; };
    priority_queue<T, vector<T>, decltype(compareC)> minHeap(compareC);
    priority_queue<T, vector<T>, decltype(compareP)> maxHeap(compareP);

    for (int i = 0; i < Capital.size(); ++i)
      minHeap.emplace(Profits[i], Capital[i]);

    while (k--) {
      while (!minHeap.empty() && minHeap.top().cap <= W)
        maxHeap.push(minHeap.top()), minHeap.pop();
      if (maxHeap.empty())
        break;
      W += maxHeap.top().pro, maxHeap.pop();
    }

    return W;
  }
};




			


class T {
  public int pro;
  public int cap;
  public T(int pro, int cap) {
    this.pro = pro;
    this.cap = cap;
  }
}

class Solution {
  public int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) {
    Queue<T> minHeap = new PriorityQueue<>((a, b) -> a.cap - b.cap);
    Queue<T> maxHeap = new PriorityQueue<>((a, b) -> b.pro - a.pro);

    for (int i = 0; i < Capital.length; ++i)
      minHeap.offer(new T(Profits[i], Capital[i]));

    while (k-- > 0) {
      while (!minHeap.isEmpty() && minHeap.peek().cap <= W)
        maxHeap.offer(minHeap.poll());
      if (maxHeap.isEmpty())
        break;
      W += maxHeap.poll().pro;
    }

    return W;
  }
}