Recognize if not enough resources during timeframe

Question

i need an idea how to solve the following problem.

Lets say i have one group with given timeframe (8:00-12:00) and i can assign resources (people) to it. Each resource can have a custom timeframe (like 9-10, 9-12,8-12 etc.) and could be assigned multiple times.

Tables

Groups

ID, TITLE, START_TIME, END_TIME, REQUIRED_PEOPLE:INTEGER

PeopleAssignments

ID, USER_ID, GROUP_ID, START_TIME, END_TIME

Now i have the rule that at any given time during the group timeframe that there have to be like like 4 people assigned. Otherwise i want to get a warning.

I am working with ruby & sql (Postgres) here.

is there an elegant way without iterating through the whole timeframe and checking if count(assignments) > REQUIRED_PEOPLE

Answer 1

In any case you need to query number of assignment in DB. There is no other way to find how many times a group assign to people.

There might be ways to find number of assignment but in the end you have to fire a query to DB.

@group = Group.find(id)
if @group.people_assignments.count >= REQUIRED_PEOPLE
  pus 'warning'
end

You can add extra column in group that hold information how many times that group assign to people. In this way one query to server reduced.

@group = Group.find(id)
if @group.count_people_assigned >= REQUIRED_PEOPLE
  puts 'warning'
end

In second case count_people_assigned is column so no extra query will execute while in first case people_assignments is association so one extra query will fire.

But in second case you have you update group each time you assign group to people. Ultimately extra query. Your choice where you want to reduce query.

My opinion is second case, It will happen rare than first.

Answer 2

You can solve this with only SQL too (if you are interested in such answers).

Range types offers great functions and operators to calculate with.

These solutions will give you rows, when there are sub-ranges, where there is some missing people from a given group (and it will give you which sub-range it is exactly & how many people is missing from the required number).

The easy way:

You wanted to try something similar to this. You'll need to pick some interval in which the count() is based on (I picked 5 minutes):

select     g.id group_id, i start_time, i + interval '5 minutes' end_time, g.required_people - count(a.id)
from       groups g
cross join generate_series(g.start_time, g.end_time, interval '5 minutes') i
left join  people_assignments a on a.group_id = g.id
where      tsrange(a.start_time, a.end_time) && tsrange(i, i + interval '5 minutes')
group by   g.id, i
having     g.required_people - count(a.id) > 0
order by   g.id, i

But note that you won't be able to detect missing sub-ranges, when they are less than 5 minutes. F.ex. user1 has assignment for 11:00-11:56 and user2 has one for 11:59-13:00, they will appear to be "in" the group for 11:00-13:00 (so the missing sub-range of 11:56-11:59 will go unnoticed).

Note: the more short the interval is (what you've picked) the more precise (and slow!) the results will be.

http://rextester.com/GRC64969

The hard way:

You can accumulate the result on-the-fly with custom aggregates or recursive CTEs

with recursive r as (
    -- start with "required_people" as "missing_required_people" in the whole range
    select 0 iteration,
           id group_id,
           array[]::int[] used_assignment_ids,
           -- build a json map, where keys are the time ranges
           -- and values are the number of missing people for that range
           jsonb_build_object(tsrange(start_time, end_time), required_people) required_people_per_time_range
    from   groups
    where  required_people > 0
    and    id = 1 -- query parameter
  union all
    select r.iteration + 1,
           r.group_id,
           r.used_assignment_ids || a.assignment_id,
           d.required_people_per_time_range
    from   r
    -- join a single assignment to the previous iteration, where
    -- the assigment's time range overlaps with (at least one) time range,
    -- where there is still missing people. when there are no such time range is
    -- found in assignments, the "recursion" (which is really just a loop) stops
    cross join lateral (
      select     a.id assignment_id, tsrange(start_time, end_time) time_range
      from       people_assignments a
      cross join (select key::tsrange time_range from jsonb_each(r.required_people_per_time_range)) j
      where      a.group_id = r.group_id
      and        a.id <> ALL (r.used_assignment_ids)
      and        tsrange(start_time, end_time) && j.time_range
      limit      1
    ) a
    -- "partition" && accumulate all remaining time ranges with
    -- the one found in the previous step
    cross join lateral (
      -- accumulate "partition" results
      select jsonb_object_agg(u.time_range, u.required_people) required_people_per_time_range
      from   (select key::tsrange time_range, value::int required_people
              from   jsonb_each_text(r.required_people_per_time_range)) j
      cross join lateral (
        select u time_range, j.required_people - case when u && a.time_range then 1 else 0 end required_people
        -- "partition" the found time range with all existing ones, one-by-one
        from   unnest(case
                 when j.time_range @> a.time_range
                 then array[tsrange(lower(j.time_range), lower(a.time_range)), a.time_range, tsrange(upper(a.time_range), upper(j.time_range))]
                 when j.time_range && a.time_range
                 then array[j.time_range * a.time_range, j.time_range - a.time_range]
                 else array[j.time_range]
               end) u
        where not isempty(u)
      ) u
    ) d
),
-- select only the last iteration
l as (
  select   group_id, required_people_per_time_range
  from     r
  order by iteration desc
  limit    1
)
-- unwind the accumulated json map
select     l.group_id, lower(time_range) start_time, upper(time_range) end_time, missing_required_people
from       l
cross join lateral (
  select key::tsrange time_range, value::int missing_required_people
  from   jsonb_each_text(l.required_people_per_time_range)
) j
-- select only where there is still some missing people
-- this is optional, if you omit it you'll also see row(s) for sub-ranges where
-- there is enough people in the group (these rows will have zero,
-- or negative amount of "missing_required_people")
where      j.missing_required_people > 0

http://rextester.com/GHPD52861