Crypto Block Mining Selection
MediumSorting · Coinbase
A miner fills a block greedily. You are given parallel lists transaction_ids, fees and sizes (transaction i has id transaction_ids[i], pays fees[i], and takes sizes[i] bytes), plus the block capacity block_size in bytes.
First rank all transactions by priority:
- Higher fee-per-byte ratio
fees[i] / sizes[i]first. - If ratios are equal, higher absolute fee first.
- If still tied, smaller size first.
- If still tied, lexicographically smaller transaction id first.
Then walk the ranked list once. Include a transaction if it fits in the remaining space; otherwise skip it and keep going, since a later, smaller transaction may still fit.
Return the ids of the included transactions in the order they were included.
Example 1
- Input:
- transaction_ids = ["tx1", "tx2", "tx3", "tx4", "tx5"], fees = [50, 60, 30, 40, 9], sizes = [50, 30, 20, 40, 3], block_size = 100
- Output:
- ["tx5", "tx2", "tx3", "tx4"]
- Explanation
- Fee-per-size ratios are 1.0, 2.0, 1.5, 1.0 and 3.0, so the order is tx5, tx2, tx3, then tx1 before tx4 (same ratio, larger fee). tx5, tx2 and tx3 use 53 bytes; tx1 (50) would exceed 100 and is skipped, but tx4 (40) still fits.
Example 2
- Input:
- transaction_ids = ["a", "b", "c"], fees = [10, 20, 20], sizes = [10, 20, 20], block_size = 25
- Output:
- ["b"]
- Explanation
- All three have ratio 1.0. b and c tie on fee and size, so the smaller id
bgoes first. After b (20), neither c (20) nor a (10) fits in the remaining 5.
Example 3
- Input:
- transaction_ids = ["big", "small"], fees = [100, 1], sizes = [200, 1], block_size = 150
- Output:
- ["small"]
- Explanation
smallhas ratio 1.0 andbigonly 0.5, sosmallgoes first even thoughbigpays far more.bigneeds 200 bytes, more than the whole block, so it is skipped.
Constraints
1 <= transaction_ids.length <= 10^5fees.length == sizes.length == transaction_ids.length0 <= fees[i] <= 10^9,1 <= sizes[i] <= 10^90 <= block_size <= 10^12- Transaction ids are unique