Maximize Center A Package Benefit
Amazon● MediumINTERNOAProblem statement
Two distribution centers, A and B, must allocate n packages. Package i is worth benefitA[i] to Center A and benefitB[i] to Center B.
The array linkedPairs contains disjoint pairs [x, y]. For each linked pair, exactly one package goes to A and the other goes to B; A receives whichever of the two packages has the larger A-benefit. Packages that do not appear in any linked pair are independent.
Order the independent packages by decreasing benefitA[i] + benefitB[i], breaking a tie by smaller package index. Center A receives the first independent package in that order and then every other package; Center B receives the remaining independent packages.
Examples
Example 1
benefitA = [8,3,7,4]benefitB = [1,9,2,6]linkedPairs = [[0,1]]return = 12From linked pair [0,1], A takes package 0 for benefit 8. Independent packages 2 and 3 have combined benefits 9 and 10, so their order is 3,2. A receives package 3 for another 4, giving 12.
Unlock this recently reported problem
FastPrep Pro gives you full access to interview problems reported within the last week.
- Full problem statement and constraints
- 2 more worked examples, explained
- Guided hints and editorial
- Run your code on real test cases
$99 billed yearly — or $19 month-to-month. Cancel anytime.