At the start of term, students swap copies of one required textbook. Each buyer wants one copy and would pay at most their value for it (in dollars); each seller has one copy and would part with it for no less than their cost. Values and costs are whole numbers.
A set of trades pairs some buyers with some sellers, one copy each. Its total surplus is the sum of the values of the buyers who get a copy minus the sum of the costs of the sellers who give one up. The efficient quantity is the number of trades in a set with the largest possible total surplus; if trading one more copy would add exactly 0, it still counts, so report the largest such number.
A single price p can organise those trades if, at p, nobody wants to change sides: every buyer who gets a copy has a value of at least p, every buyer left out has a value of at most p, every seller who sells has a cost of at most p, and every seller who keeps their copy has a cost of at least p. These prices form a range from low to high.
Write double_auction(values, costs) that returns the tuple (quantity, surplus, low, high) for the efficient quantity, the largest total surplus, and the ends of the range of prices.
Examples
Input: values = [40, 25, 32, 10, 18], costs = [12, 30, 8, 22, 35]
Output: (3, 55, 22, 25)
Explanation: the buyers valuing 40, 32 and 25 get the copies of the sellers with
costs 8, 12 and 22. Any price from 22 to 25 works: at 21 the seller with cost 22
would refuse, and at 26 the buyer with value 25 would.
Input: values = [20], costs = [25]
Output: (0, 0, 20, 25)
Explanation: no trade. Any price from 20 to 25 leaves both happy to stay out.
Input: values = [30, 30], costs = [30]
Output: (1, 0, 30, 30)
Constraints
- answers are whole numbers
Goals
- Find the trades that make total surplus as large as possible by sorting both sides
- Count the efficient number of trades, including a trade that adds exactly zero
- Find the whole range of prices that support those trades