FastPrep
Problem · Greedy

Maximize Ad-Slot Revenue

Learn this problem
● MediumAmazon logoAmazonFULLTIMEONSITE INTERVIEW
See Amazon hiring insights

Problem statement

You have slots identical advertising slots. Company i requests up to requestedSlots[i] slots and pays revenuePerSlot[i] for each slot it receives.

You may partially fulfill any request. Allocate at most slots total slots and return the maximum revenue. If total demand is smaller than the capacity, unused slots are allowed.

Function

maximizeRevenue(slots: int, requestedSlots: int[], revenuePerSlot: int[]) → long

Examples

Example 1

slots = 4requestedSlots = [3,2,4]revenuePerSlot = [5,8,3]return = 26

Give two slots to the offer paying 8 and the remaining two to the offer paying 5.

Example 2

slots = 6requestedSlots = [2,3]revenuePerSlot = [4,4]return = 20

Only five slots are requested, so one slot remains unused.

Constraints

  • 0 <= slots <= 10^9
  • 1 <= requestedSlots.length = revenuePerSlot.length <= 100000
  • 0 <= requestedSlots[i], revenuePerSlot[i] <= 10^9
  • The answer fits in a signed 64-bit integer.

More Amazon problems

drafts saved locally
public long maximizeRevenue(int slots, int[] requestedSlots, int[] revenuePerSlot) {
    // Write your code here.
}
slots4
requestedSlots[3,2,4]
revenuePerSlot[5,8,3]
expected26
checking account