code: def get_rules_for_shard_optimal(
      rules_grouped_by_time: List[Tuple[float, List[BazelRule]]],
      index: int,
      count: int,
  ) -> List[str]:
      """Creates shards by trying to make sure each shard takes around the same time.
  
      We use a simple heuristic here (as this problem is NP-complete):
      1. Determine how long one shard would take if they were ideally balanced
         (this may be impossible to attain, but that's fine).
      2. Allocate the next biggest item into the first shard that is below the optimum.
      3. If there's no shard below optimium, choose the shard closest to optimum.
  
      This works very well for our usecase and is fully deterministic.
  
      ``rules_grouped_by_time`` is expected to be a list of tuples of
      (timeout in seconds, list of rules) sorted by timeout descending.
      """
      # For sanity checks later.
      all_rules = []
      for _, rules in rules_grouped_by_time:
          all_rules.extend(rules)
  
      # Instantiate the shards, each represented by a list.
      shards: List[List[BazelRule]] = [list() for _ in range(count)]
  
      # The theoretical optimum we are aiming for. Note that this may be unattainable
      # as it doesn't take into account that tests are discrete and cannot be split.
      # This is however fine, because it should only serve as a guide which shard to
      # add the next test to.
      optimum = (
          sum(
              timeout * len(rules)
              for timeout, rules in rules_grouped_by_time
          )
          / count
      )
  
      def get_next_longest_rule() -> BazelRule:
          """
          Get the next longest (taking up the most time) BazelRule from the
          ``rules_grouped_by_time`` list.
          """
          item = None
          for _, items in rules_grouped_by_time:
              if items:
                  return items.pop()
          return item
  
      rule_to_add = get_next_longest_rule()
      while rule_to_add:
          add_rule_to_best_shard(rule_to_add, shards, optimum)
          rule_to_add = get_next_longest_rule()
  
      # Sanity checks.
      num_all_rules = sum(len(shard) for shard in shards)
  
      # Make sure that there are no duplicate rules.
      all_rules_set = set()
      for shard in shards:
          all_rules_set = all_rules_set.union(set(shard))
      assert len(all_rules_set) == num_all_rules, (
          f"num of unique rules {len(all_rules_set)} "
          f"doesn't match num of rules {num_all_rules}"
      )
  
      # Make sure that all rules have been included in the shards.
      assert all_rules_set == set(all_rules_set), (
          f"unique rules after sharding {len(all_rules_set)} "
          f"doesn't match unique rules after sharding {num_all_rules}"
      )
  
      print(
          f"get_rules_for_shard statistics:\n\tOptimum: {optimum} seconds\n"
          + "\n".join(
              (
                  f"\tShard {i}: {len(shard)} rules, "
                  f"{sum(rule.actual_timeout_s for rule in shard)} seconds"
              )
              for i, shard in enumerate(shards)
          ),
          file=sys.stderr,
      )
      return sorted([rule.name for rule in shards[index]])
  
imports: from collections import defaultdict
  from dataclasses import dataclass
  from typing import Iterable, List, Optional, Set, Tuple
  import argparse
  import os
  import re
  import shlex
  import subprocess
  import sys
  import xml.etree.ElementTree
label_desc: Use image node_id 11 for calling a global function with example usage: get_rules_for_shard_optimal(rules_grouped_by_time, index, count) and returns: sorted, item, items