Graph Theory37 sections · 1633 units
Open in Course

Application - Scheduling

(Time slots and tasks)

You have nn tasks and mm time slots. Each task can be completed in certain time slots based on availability constraints. Schedule the maximum number of tasks such that each time slot handles at most one task. Model as bipartite matching: tasks are group LL, time slots are group RR.

An edge means task ii can use slot jj. The maximum matching gives you the maximum number of tasks you can schedule without conflicts.