Test shard partitions
A continuous integration runner spreads a suite across parallel shards. test_names lists the tests in suite order and test_seconds[i] is how long test i runs. Every test lands on exactly one shard, every shard gets at least one test, the runner is configured for exactly shard_count shards, and no shard may total more than shard_limit seconds. Shards carry no numbers, so two plans that group the same tests together are one plan however the shards happen to be ordered. Return every distinct plan as a string: inside a shard the names keep suite order joined by a plus sign, shards are ordered by the suite position of their first test, and shards are joined by a space, a pipe and a space. Sort the plans in ascending order. Return an empty list when no plan works and when there are no tests. Names are distinct and carry no plus sign or space. There are at most 9 tests and shard_count is at least 1.
list_shard_splits(test_names: list[str], test_seconds: list[int], shard_count: int, shard_limit: int) → list[str][["auth","db","ui"],[3,4,2],2,6]out["auth | db+ui","auth+ui | db"][["a","b","c","d"],[1,1,1,1],2,2]out["a+b | c+d","a+c | b+d","a+d | b+c"][["lint","unit"],[5,5],1,10]out["lint+unit"]State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.
[["auth","db","ui"],[3,4,2],2,6]["auth | db+ui","auth+ui | db"]not run yetsample[["a","b","c","d"],[1,1,1,1],2,2]["a+b | c+d","a+c | b+d","a+d | b+c"]not run yetsample[["lint","unit"],[5,5],1,10]["lint+unit"]not run yetsample