Route to the Cheapest Model Meeting Quality

1. Background Knowledge

This problem simulates a model router in a production AI system, where cost and quality are competing objectives. In real-world deployments, teams often maintain a fleet of models with different capability tiers and price points. The router’s job is to select the most cost-effective model that still meets a minimum quality threshold for a given task. This is a common pattern in cost-aware inference pipelines, where you want to avoid paying for a large, expensive model when a smaller one can handle the job adequately.

The core logic involves two distinct selection modes. In the primary mode, you filter for models that satisfy a quality constraint and then optimize for cost. In the fallback mode, triggered when no model meets the quality bar, you simply pick the best available model by quality, ignoring cost. Both modes require careful handling of tie-breaking rules, which are specified to ensure deterministic output when multiple models have identical scores.

Understanding lexicographic sorting is key here. When you need to pick a "best" model based on multiple criteria (e.g., lowest price, then highest quality, then alphabetical name), you are effectively defining a total order over the models. Python’s min and max functions accept a key argument that lets you define this ordering explicitly, making it straightforward to implement complex tie-breaking logic without writing manual comparison loops.

2. Algorithm Approach

The approach is a filter-then-optimize strategy with a fallback branch.

1. Filter: Create a subset of models where quality >= min_quality.
2. Primary Selection: If the subset is non-empty, find the model with the lowest price. If prices are tied, prefer the higher quality. If quality is also tied, prefer the lexicographically smaller name.
3. Fallback Selection: If the subset is empty, find the model with the highest quality from the full list. If qualities are tied, prefer the lower price. If prices are also tied, prefer the lexicographically smaller name.

This is not a dynamic programming or graph problem; it is a straightforward selection problem with conditional logic. The key insight is that the tie-breaking rules differ between the primary and fallback paths, so you cannot use a single sort key for both cases.

3. Step-by-Step Strategy

1. Define the primary key function: For the primary path, you want the "cheapest" model. In Python, min finds the smallest element. So, define a key that returns a tuple: (price, -quality, name). Using -quality ensures that higher quality comes first when prices are equal (since min picks the smallest tuple, and a more negative number is smaller). The name ensures alphabetical tie-breaking.
2. Filter the models: Use a list comprehension to create qualified = [m for m in models if m["quality"] >= min_quality].
3. Check if qualified is empty:

• If not empty: Apply min(qualified, key=primary_key) and return the name of the result.
• If empty: You need the fallback. Define a secondary key function for the fallback path. You want the "highest quality" model. Use max with a key that returns (quality, -price, name). Here, max picks the largest tuple. Higher quality is better. If quality is tied, you want the lower price, so use -price (since a more negative number is smaller, but max picks the largest, so you actually want the smallest price to be "best" in the tie-break. Wait, let's re-evaluate).