javascriptalgorithmperformancedatetimematrix

Efficiently calculate an availability date from a list of project assignments and known capacity


I'm looking for an efficient way to calculate the date each member of a team is available given a set of project assignments. There are 25 team members, each with a set of capacities and assignments.

Capacities are a percentage availability between two dates (this is how part-time hours are supported, 100% being full-time), with null end dates for scenarios where the capacity is indefinite. Capacities can be zero, to support things such as secondments or parental leave.

Assignments link a team member to a project for a percentage between two dates. This allows a member to have two projects at the same time (say a 60/40 split) and these add up to the capacity of the team member. So if a person has 60% capacity, they might have two projects 30% each.

All of this works perfectly, but now I want to calculate the date each person in the team is available next. I can do this in what feels like a brute-force way by using a loop to count forward one day at a time until I arrive at a point where the total assigned percentage is less than the capacity, but this feels wildly inefficient - is there a better way?

I've added a Gantt chart image to show what I mean, I'd like to calculate the dates where the red lines are. Any help, even pseudo-code, is greatly appreciated. The application stack is NodeJS and Vue, and I'm using the Luxon library in the brute-force method. Language doesn't matter, I'm looking for help with the general approach to the problem that I can then implement in JS.

enter image description here


Solution

  • I can do this in what feels like a brute-force way by using a loop to count forward one day at a time until I arrive at a point where the total assigned percentage is less than the capacity, but this feels wildly inefficient - is there a better way?

    There's no need to do that one day at a time. If you have the capacities and assignments of the team member, all you need to do is look at the dates on which the percentages change - not at each day until you find a solution (which might be never if they have an indefinite 0% capacity).

    Sort the events by date, then process them in order, until you reach either the end of the events or find a date where capacity will exceed assignments. Since you may need only a few events until that point, you don't even have to sort the entire list of events, but can do it lazily, e.g. with a min heap.