Volume (Tiered) Pricing

Medium Greedy / Math 3 parts 85 lines View on GitHub ↗

Question

Topic: Greedy / Math · Difficulty: Easy → Medium

Price tiers are [upTo, unitPrice], ordered by upTo; -1 means “and above”. Example: [[10, 50], [20, 40], [-1, 30]] means units 1–10 cost 50, 11–20 cost 40, and 21+ cost 30.

Part 1: all-units pricing

Find the tier the quantity falls into. Every unit is charged that tier’s price.

Part 2: graduated pricing

Each unit is charged by the tier it falls in (like tax brackets): 15 units = 10 × 50 + 5 × 40 = 700.

Part 3: maximum quantity for a budget

Given a budget, return the most units you can buy under graduated pricing (budget = 745 → 16).

Approach: walk the tiers in order. Part 2 takes min(quantity, upTo) - alreadyCounted units per tier. Part 3 spends the budget tier by tier until it can’t fill the next tier, then divides what is left by that tier’s price.

VolumePricingPart1.java 23 lines GitHub ↗

/**
 * Problem: Volume (Tiered) Pricing
 * Difficulty: Medium
 * Topic: Greedy / Math
 * Question: Price a quantity with all-units tiers, then graduated tiers, then find the most units a budget buys. Full statement in README.md.
 */
package dsa.question4;

public class VolumePricingPart1 {

    public static long calculatePrice(int[][] tiers, int quantity) {
        int n = tiers.length,i=0;
        if(quantity <= 0) {
            return 0;
        }
        for(i=0;i<n;i++) {
            if(tiers[i][0] == -1) {
                return (long)quantity*tiers[i][1];
            }else if(tiers[i][0] >= quantity) {
                return (long)quantity*tiers[i][1];
            }
        }
        return 0;
    }
}

VolumePricingPart2.java 21 lines GitHub ↗

package dsa.question4;

public class VolumePricingPart2 {

    public static long calculatePrice(int[][] tiers, int quantity) {
        int n = tiers.length , ed=0 , remainingQty = quantity;
        long ans=0;
        while(remainingQty > 0 && ed < n) {
            int upto = tiers[ed][0], cost = tiers[ed][1];

            if(upto == -1) {
                ans += (long) remainingQty * cost;
                remainingQty = 0;
            }else {
                int excluded = quantity-remainingQty ;
                int include = Math.min(quantity, upto) - excluded;
                ans += (long) include * cost;
                remainingQty = remainingQty - include;
            }

            ed++;
        }
        return ans;
    }
}

VolumePricingPart3.java 23 lines GitHub ↗

package dsa.question4;

public class VolumePricingPart3 {

    public static long calculatePrice(int[][] tiers, long budget) {
        int n = tiers.length , ed=0;
        long remainingbudget = budget;
        long quantity = 0;
        while(remainingbudget > 0 && ed < n) {
            int upto = tiers[ed][0], cost = tiers[ed][1];
            long number = remainingbudget/cost;
            if(upto == -1) {
                return quantity + number;
            }else if (number + quantity < upto) {
                return quantity + number;
            } else {
                long take = upto - quantity;
                remainingbudget -= (long) cost * take;
                quantity = upto;
            }
            ed++;
        }
        return quantity;
    }
}

Demo.java 18 lines GitHub ↗

package dsa.question4;

public class Demo {

    public static void main(String[] args) {
        //Input: tiers = [[10, 50], [20, 40], [-1, 30]], quantity = 8

//        int[][] tiers = {{10, 50} , {20, 40} , {-1, 30}};
//        int quantity = 25;
//        long output = VolumePricingPart1.calculatePrice(tiers , quantity);
//        System.out.println(output);

//        int[][] tiers = {{10, 50} , {20, 40} , {-1, 30}};
//        int quantity = 15;
//        long output = VolumePricingPart2.calculatePrice(tiers , quantity);
//        System.out.println(output);

        int[][] tiers = {{10, 50} , {20, 40} , {-1, 30}};
        int budget = 745;
        long output = VolumePricingPart3.calculatePrice(tiers , budget);
        System.out.println(output);

    }

}