Merge Two Job Queues With the Fewest Urgency Inversions

A print shop runs two job queues, one from the web store and one from the walk-in counter. Every job has an urgency digit from 0 (most urgent) to 9 (least urgent). The shop is replacing both queues with a single printer, so the two queues must be merged into one sequence that keeps each queue's internal order. Any interleaving is allowed.

An inversion is any pair of jobs where a less urgent job (larger digit) is scheduled before a more urgent job (smaller digit). Every such pair counts once, including pairs from the same original queue, which no merge can fix.

Return the minimum number of inversions over all valid merges.

def min_merge_inversions(left: str, right: str) -> int:

left and right are strings of digits, each listing a queue's urgency digits from front to back.

Rules

• The merged sequence has length len(left) + len(right) and uses every job exactly once.
• The jobs of left appear in their original relative order, and so do the jobs of right.
• A pair of positions x < y is an inversion if merged[x] > merged[y]. Equal digits never form an inversion.

Examples

Example 1

left = "31", right = "20"
Output: 3

Two inversions are unavoidable (3 before 1, and 2 before 0). The merge 2 0 3 1 adds only one more (2 before 1). Every other merge adds at least one, so the answer is 3.

Example 2

left = "402", right = "13"
Output: 4

The merge 1 4 0 2 3 has inversions (1,0), (4,0), (4,2) and (4,3). No merge does better.

Example 3

left = "5", right = "5"
Output: 0

Constraints

• 1 <= len(left), len(right) <= 1000
• Both strings contain only the characters '0' to '9'.
• The answer fits in a 64-bit integer.