We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Greedy
  4. Greedy Florist
  5. Discussions

Greedy Florist

Sort by

recency

|

794 Discussions

|

  • rajivaiyer
     + 0 comments

    My Java 8 solution, which passes all test cases, for max score of 35:

    Code is fairly simple & self-explanatory.

    Sort the Array + simple greedy approach after that.

        // Complete the getMinimumCost function below.
    static int getMinimumCost(int k, int[] c) {
        int minFlowerCost = 0;

        int numFriends = k;
        int numFlowers = c.length;
        
        Arrays.sort(c);
        
        List<Integer> friendNumFlowers = 
            IntStream.range(0, numFriends)
                .mapToObj(i -> 0)
                .collect(Collectors.toCollection(ArrayList::new));

        int friendIdx = 0;
        for (int cIdx = (numFlowers - 1) ; cIdx >= 0 ; cIdx--) {
            minFlowerCost += ((friendNumFlowers.get(friendIdx) + 1) * c[cIdx]);
            friendNumFlowers.set(friendIdx, (friendNumFlowers.get(friendIdx) + 1));
            friendIdx = ((friendIdx + 1) % numFriends);
        }
        
        return minFlowerCost;
    }

  • patrickgao2020
     + 0 comments

    Here is my Python solution!

    def getMinimumCost(k, c):
    flowers = len(c)
    c.sort()
    price = 0
    for multiplier in range(1, flowers // k + 1):
        for num in range(k):
            price += multiplier * c.pop()
    price += sum(c) * (flowers // k + 1)
    return price

  • pelotasplus
     + 0 comments
    def getMinimumCost(k, c):
    c.sort(reverse = True)
    sum = 0
    for idx, price in enumerate(c):
        sum += price * (1 + idx // k)
    return sum

  • schmiddla
     + 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;
}

  • ercanbeyen
     + 0 comments

    Java Solution

    import java.util.*;

public class Solution {

    static int getMinimumCost(int numberOfFriends, Integer[] prices) {
        Arrays.sort(prices, Collections.reverseOrder());

        int i = 0;
        int numberOfBoughtFlowers = 0;
        int minimumCost = 0;
        
        while (i < prices.length) {
            for (int j = 0; j < numberOfFriends && i < prices.length; j++) {
                minimumCost += (1 + numberOfBoughtFlowers) * prices[i];
                i++;
            }
            
            numberOfBoughtFlowers++;
        }
        
        return minimumCost;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        final String SPACE = " ";
        String[] amounts = scanner.nextLine().split(SPACE);
        int numberOfFlowers = Integer.parseInt(amounts[0]);
        int numberOfFriends = Integer.parseInt(amounts[1]);

        Integer[] prices = new Integer[numberOfFlowers];
        String[] priceItems = scanner.nextLine().split(SPACE);

        for (int i = 0; i < numberOfFlowers; i++) {
            int price = Integer.parseInt(priceItems[i]);
            prices[i] = price;
        }

        int minimumCost = getMinimumCost(numberOfFriends, prices);
        System.out.println(minimumCost);
        
        scanner.close();
    }
}