Prefix-intersection merging can be simplified to the following:
- Given two linearizations L_1 and L_2
- (Optionally) Output any prefix of both that’s identical.
- Let P_i be the highest-feerate prefix of L_i, for i \in {1,2}.
- Assume without loss of generality that R(P_1) \geq R(P_2) (swap the inputs if not).
- Let C be the highest-feerate prefix of L_2 \cap P_1.
- Output C, remove it from L_1 and L_2, and start over.
So we only need to find the best prefix of the intersection of the highest-feerate prefix with the other linearization, and not the other direction.
This does not break the “as good as both inputs” proof, and from fuzzing it appears it that this doesn’t worsen the result even (it could be that this results in worse results while still being at least as good as both inputs, but that seems not to be the case).
I don’t have a proof (yet) that the algorithms are equivalent, but given that it’s certainly correct still, it’s probably fine to just use this simpler version?