Load-Balanced Assignment Coding

HardPython

Problem

Implement a load balancer for Intercom Inbox conversations. Assign conversations in arrival order to an eligible teammate while respecting required skills and capacity. Choose the eligible teammate with the smallest projected utilization after assignment, breaking ties by lower current load and then lexicographically smaller teammate ID.

A conversation cannot be assigned if no eligible teammate has enough remaining capacity. Each conversation is assigned at most once.

Formal Specification

Implement assign_conversations(agents, conversations).

agents is a list of objects with string id, list skills, and positive integer capacity. An optional integer load gives the teammate's initial load and defaults to 0.
conversations is a list of objects with string id, list required_skills, and positive integer effort.
Return an object with assignments, a mapping from conversation ID to teammate ID, and unassigned, a list of conversation IDs that could not be assigned.
A teammate is eligible when their skills contain every required skill and load + effort <= capacity.
Projected utilization is (load + effort) / capacity.

Constraints

1 <= len(agents), len(conversations) <= 10^5
1 <= capacity, effort <= 10^9
Each agent has at most 20 skills
Skills and IDs are non-empty strings
Agent IDs and conversation IDs are unique

Function Signature

def assign_conversations(agents, conversations):

A conversation cannot be assigned if no eligible teammate has enough remaining capacity. Each conversation is assigned at most once.

Formal Specification

Implement assign_conversations(agents, conversations).

agents is a list of objects with string id, list skills, and positive integer capacity. An optional integer load gives the teammate's initial load and defaults to 0.
conversations is a list of objects with string id, list required_skills, and positive integer effort.
Return an object with assignments, a mapping from conversation ID to teammate ID, and unassigned, a list of conversation IDs that could not be assigned.
A teammate is eligible when their skills contain every required skill and load + effort <= capacity.
Projected utilization is (load + effort) / capacity.