In this follow-up question, each transaction now carries an optional parentId field. A parentId points to another transaction in the mempool that must be mined in the same block before the child transaction can be included.
- A parent can have multiple children, but a child has at most one parent. No cycles are possible.
- Child-Pays-For-Parent (CPFP): When evaluating a child transaction's priority, consider the combined fee and combined size of the child plus all its unmined ancestors (traversing up the chain to the root or the nearest already-mined ancestor).
- Once a parent is mined, its cost is "paid for." Any child of an already-mined parent is evaluated using only its own remaining unmined ancestors.
- If
parentIdis an empty string, the transaction has no prerequisites.
Extend mineBlock function with an additional parentIds parameter to account for these dependencies to achieve the best fee-to-size ratio. Return the selected transaction IDs in any order.
Example 1:
Input: transactionIds = ["tx1", "tx2", "tx3", "tx4"], fees = [10, 100, 40, 50], sizes = [50, 20, 30, 30], parentIds = ["", "tx1", "", ""], blockSize = 100 Output: ["tx4", "tx1", "tx2"] Explanation: "tx2" depends on "tx1", and their package has a combined fee of 110 and a combined size of 70, giving an effective ratio of ≈1.57. "tx3" has ratio ≈1.33, and "tx4" has ratio ≈1.67. Therefore, the miner selects "tx4", "tx1", and "tx2".
Example 2:
Input: transactionIds = ["tx1", "tx2", "tx3"], fees = [10, 80, 25], sizes = [20, 10, 20], parentIds = ["", "tx1", ""], blockSize = 50 Output: ["tx1", "tx2", "tx3"]
Example 3:
Input: transactionIds = ["tx1", "tx2", "tx3"], fees = [10, 80, 30], sizes = [20, 10, 10], parentIds = ["", "tx1", "tx1"], blockSize = 40 Output: ["tx1", "tx2", "tx3"]
