Fastest parallel test shard
Your task
A build team timed every subset of its k test files as a single shard, so shard_time has 2^k entries and shard_time[m] is the measured wall time of the shard holding exactly the files named by mask m, setup included. Entry 0 is the empty shard and takes no time. Instead of running a subset whole, the team can split it into two groups, neither of them empty, that run on separate machines at the same time, and either group can be split again the same way. A split finishes when its slower side finishes, and machines are never scarce. Return one entry per subset, in mask order, holding the earliest that subset can finish. k is at most 12. An empty table returns an empty list.
Examples
shard_finish_times(shard_time: list[int]) -> list[int]Example 1
Input
shard_finish_times([0, 10, 12, 30])Output
[0, 10, 12, 12]Example 2
Input
shard_finish_times([0, 5, 5, 4])Output
[0, 5, 5, 4]Example 3
Input
shard_finish_times([0, 8, 6, 20, 9, 30, 24, 40])Output
[0, 8, 6, 8, 9, 9, 9, 9]