Mentorship and Leadership at Scale Questions

from collections import defaultdict

def greedy_match(mentors, mentees):
    """
    mentors: list of dicts: {'id': int, 'skills': set(str), 'capacity': int}
    mentees: list of dicts: {'id': int, 'desired': set(str)}
    returns: dict mentee_id -> mentor_id (only matched mentees)
    """
    # Build helper maps
    mentor_caps = {m['id']: m['capacity'] for m in mentors}
    mentor_skills = {m['id']: set(m['skills']) for m in mentors}
    matches = {}

    # Precompute for each mentee their list of candidate mentors and overlap counts
    mentee_candidates = {}
    for mt in mentees:
        cand = []
        for mid, mskills in mentor_skills.items():
            overlap = len(mskills & set(mt['desired']))
            if overlap > 0 and mentor_caps[mid] > 0:
                cand.append((mid, overlap))
        mentee_candidates[mt['id']] = cand

    # Sort mentees by number of candidates (ascending) to handle constrained first
    mentees_sorted = sorted(mentees, key=lambda x: (len(mentee_candidates[x['id']]) , -len(x['desired'])))

    for mt in mentees_sorted:
        cid = mt['id']
        # refresh candidates to consider current capacities
        cand = []
        for mid, mskills in mentor_skills.items():
            if mentor_caps[mid] <= 0:
                continue
            overlap = len(mskills & set(mt['desired']))
            if overlap > 0:
                cand.append((overlap, mid))
        if not cand:
            continue
        # pick mentor with max overlap, tie-breaker: more remaining capacity
        cand.sort(reverse=True)  # largest overlap first; if tie, arbitrary by id
        best_overlap = cand[0][0]
        # among those with best_overlap, pick mentor with largest remaining capacity
        best = max((mid for ov, mid in cand if ov == best_overlap), key=lambda m: mentor_caps[m])
        matches[cid] = best
        mentor_caps[best] -= 1

    return matches