Support Desk Ticket-Analyst Matching - LSEG London Stock Exchange Online Assessment RNS Institute

Problem Preview

"Write `solution(tickets, analysts)`. Tickets: `[ticket_id, domain, complexity, priority]`. Analysts: `[analyst_id, domains, skill]`. An analyst can handle a ticket iff the ticket's domain is one of the analyst's domains, and `analyst.skill ≥ ticket.complexity` (equal is enough). Each analyst assigned to ≤1 ticket; each ticket assigned to ≤1 analyst. Choose an assignment to **maximise, in this strict order**: 1. number of P1 tickets assigned 2. then (without reducing that), number of P2 tickets assigned 3. then (without reducing either), total tickets assigned (any priority, including P3) Return `[p1_assigned, p2_assigned, total_assigned]` — you do **not** need to return which ticket went to which analyst. **Why not just "sort by priority, greedily grab first free analyst"?** This is a genuine maximum bipartite matching problem. A naive greedy can under-count P1 tickets by burning an analyst on a P1 ticket that had another option, when that analyst was the *only* one who could cover a different P1 ticket. **Correct approach**: maximum bipartite matching (Kuhn's algorithm / augmenting paths), computed tier by tier: 1. Build compatibility graph: edge between ticket t and analyst a iff a supports t's domain and a's skill ≥ t's complexity. 2. Order tickets: all P1 first, then all P2, then all P3 (stable; any order within a tier works). 3. Process tickets one at a time in that order using standard augmenting-path bipartite matching — for each new ticket, try to find an augmenting path to a free analyst through the *current* partial matching. This may reassign an already-matched ticket to a different analyst along the path (expected/required, not a bug). 4. `p1_assigned` = matched-ticket count right after all P1 tickets; `p2_assigned` = (matched count after P1+P2) − p1_assigned; `total_assigned` = matched count after all three tiers. **Constraints**: 0 ≤ length(tickets), length(analysts) ≤ 40; complexity, skill ∈ [1,5]; each analyst supports 1–6 distinct domains; priority ∈ {P1,P2,P3}. **Example 1** ``` tickets = [["T1","network",2,"P1"], ["T2","security",3,"P2"], ["T3","network",1,"P3"]] analysts = [["A1",["network","security"],3], ["A2",["network"],2]] ``` Output: `[1, 1, 2]` (T1→A1. T2 needs security, only A1 supports it — reassign T1→A2, freeing A1 for T2. T3 needs network, but both A1/A2 are taken and neither can move — T3 stays unassigned.) **Example 2 (the ambiguous case — where naive greedy fails)** ``` tickets = [["T1","network",1,"P1"], ["T2","security",1,"P1"], ["T3","network",1,"P3"]] analysts = [["A1",["network","security"],5], ["A2",["network"],5]] ``` Output: `[2, 0, 2]` (Correct: T1→A1, then T2 needs security → reassign T1→A2, T2→A1 → both P1 tickets matched, p1_assigned=2. A naive "greedy, never reassign" strategy instead assigns A1→T1, then can't place T2 — so it matches A2→T3 in the P3 tier instead, returning [1,0,2]: same total, but wrong p1_assigned. This trade — a P1 match for a P3 match of equal total size — is never allowed; P1 count must be maximised first, independent of what that does to the total.) **Edge cases**: empty tickets, empty analysts, or no compatible pair at all → `[0, 0, 0]`. Duplicate complexity/skill values across tickets/analysts are expected. Ordering of tickets/analysts in the input never affects the three output counts.  "