You are building a transaction selection system for a cryptocurrency miner. The miner selects transactions from a pending pool known as the mempool and packs them into a candidate block.
Each block has a fixed capacity blockSize. Since the miner collects the fee from every included transaction, the objective is to maximize the total fees while ensuring the block's size limit is not exceeded.
You are given three parallel arrays transactionIds, fees, and sizes, each of length N. Implement the mineBlock function to return the IDs of the transactions chosen for the block.
Transactions are prioritized based on their fee-to-size ratio. For the transaction, the ratio is computed as fees[i] / sizes[i]. A higher ratio indicates a higher priority for inclusion.
If two transactions have the same ratio, apply the following tie-breaking rules in order:
- Prefer the transaction with the higher fee.
- If still tied, prefer the transaction with the smaller size.
- If a tie remains, prefer the transaction with the lexicographically smaller ID.
Return the selected transaction IDs in any order.
Constraints:
- 1 ≤
N≤ 105 - 1 ≤
sizes[i]≤blockSize≤ 109 - 0 ≤
fees[i]≤ 106
Example 1:
Input: transactionIds = ["tx1", "tx2", "tx3", "tx4"], fees = [50, 60, 30, 40], sizes = [50, 30, 20, 40], blockSize = 100 Output: ["tx2", "tx3", "tx1"] Explanation: "tx2" has fee-to-size ratio 2.0, "tx3" has 1.5, and both "tx1" and "tx4" have 1.0. Selecting "tx2" (size 30), "tx3" (size 20), and "tx1" (size 50) fills exactly 100 units and collects total fees of 140. Since "tx1" and "tx4" share the same ratio, "tx1" is preferred because it has a higher fee.
Example 2:
Input: transactionIds = ["tx1", "tx2"], fees = [10, 6], sizes = [5, 2], blockSize = 7 Output: ["tx2", "tx1"]
Example 3:
Input: transactionIds = ["tx1", "tx2", "tx3"], fees = [100, 40, 40], sizes = [100, 50, 50], blockSize = 100 Output: ["tx1"]
