Greedy Florist

  • + 0 comments

    JS

    function getMinimumCost(k, c) {
      let min = 0;
    
      // sort flowers - highest to lowest
      c.sort((a, b) => (a - b < 0 ? 1 : -1));
    
      for (let buyerIdx = 0; buyerIdx < k; buyerIdx++) {  // e.g. 3 friends = 3 buyers
        // with every purchase the next purchased flower gets multiplied
        let multiplier = 1;
    
        // to have the lowest possible multiplier on the hightest prices,
        //  -> buy every "k" flower (flowerIdx += k) in the price-sorted array
        for (let flowerIdx = buyerIdx; flowerIdx < c.length; flowerIdx += k) {
          min += c[flowerIdx] * multiplier++;
        }
      }
    
      return min;
    }