Optimal way to match prioritized list of tasks with available workers

Problem Match prioritized tasks with suitable workers. Details Consider a task with following properties - type and size. Based on task type, tasks are prioritized. While a worker has following properties - supported task types (multiple) and remaining size (summation of multiple task's size which can be accommodated). Workers are to be kept occupied as much as possible with matching task(s). High priority task are to be finished first/asap. Workers may have some task upfront as far as their remaining size allows them to. Note - For both task and worker, irrelevant properties for matching are omitted for brevity. Number of task may go up as high as ~500k and workers ~30. Potential Solution The simplest and straight forward solution here involves below steps - Sort list of pending tasks (based on type and few more omitted properties) Sort list of available workers (based on remaining size) Iterate over list of tasks and match it with available worker (or vice versa i.e. iterate over list of workers and match it with available task) Since the worst case time complexity is O(mn) its seems there should be some better way to achieve it. Another option could be to create separate lists of tasks (list per task type). This option too have same complexity O(mn) but only additional benefit of potential concurrent execution. P.S.: I have tried isolating the issue and described in it's minimalist form. If required feel free to comment and I could help with the relevant details.

Jun 5, 2025 - 18:00

Problem

Match prioritized tasks with suitable workers.

Details

Consider a task with following properties - type and size. Based on task type, tasks are prioritized. While a worker has following properties - supported task types (multiple) and remaining size (summation of multiple task's size which can be accommodated).

Workers are to be kept occupied as much as possible with matching task(s). High priority task are to be finished first/asap. Workers may have some task upfront as far as their remaining size allows them to.

Note - For both task and worker, irrelevant properties for matching are omitted for brevity. Number of task may go up as high as ~500k and workers ~30.

Potential Solution

The simplest and straight forward solution here involves below steps -

Sort list of pending tasks (based on type and few more omitted properties)
Sort list of available workers (based on remaining size)
Iterate over list of tasks and match it with available worker (or vice versa i.e. iterate over list of workers and match it with available task)

Since the worst case time complexity is O(m*n) its seems there should be some better way to achieve it.

Another option could be to create separate lists of tasks (list per task type). This option too have same complexity O(m*n) but only additional benefit of potential concurrent execution.

P.S.: I have tried isolating the issue and described in it's minimalist form. If required feel free to comment and I could help with the relevant details.