Algorithm to match buy and sell orders-CodePudding

I am building an online stock game. All orders are at exactly market price. There is no real "bidding", only straight buy and sell. So this should be easier. Is there an algorithm that tackles the following problem:

Different orders with different volume. For example, the following buy orders are made...

order A for 50 shares

order B for 25 shares

order C for 10 shares

order D for 5 shares

order E for 5 shares

order F for 30 shares

There is a sell order G for 100 shares.

I need to find the right combination of the above buy orders in a way that gets as close to 100 shares as possible, without going over....

The Knapsack algorithm would work, but the performance will degrade very fast with a large number of users and orders being made. Is there a more efficient way to do this?

CodePudding user response：

/*
    Given array prices, return max profit w/ 1 buy & 1 sell
    Ex. prices = [7,1,5,3,6,4] -> 5 (buy at $1, sell at $6)

    For each, get diff b/w that & min value before, store max

    Time: O(n)
    Space: O(1)
*/

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minValue = prices[0];
        int maxDiff = 0;
        
        for (int i = 1; i < prices.size(); i  ) {
            minValue = min(minValue, prices[i]);
            maxDiff = max(maxDiff, prices[i] - minValue);
        }
        
        return maxDiff;
    }
};

ref: https://github.com/neetcode-gh/leetcode/blob/main/cpp/neetcode_150/03_sliding_window/best_time_to_buy_and_sell_stock.cpp

CodePudding user response：

I am still not very clear with the example you gave in the question description, for any knapsack problem we need 2 things capacity and profit. Here you just provided capacity. Considering you just need to reach 100 as close as possible without worrying about the profit then it's much simple and can have multiple ways to do it. One way is to just take all the bigger one which is smaller than the remaining capacity. If they are bigger than the remaining capacity then go to the next smaller one. Time: O(NlogN) for sorting Space: O(1)

function getMax(arr, maxCap) {
  arr.sort((a, b) => b - a);
  let index = 0;
  let cap = 0;
  while (cap !== maxCap && index < arr.length) {
    const remainingCap = maxCap - cap;
    if (remainingCap >= arr[index]) {
      cap  = arr[index];
    }
    index  ;
  }
}