Thread: How to find earlest possible start times for given duration excluding reservations

Hi!

I'm looking for finding ealiest possible start times from reservations
table.

People work from 10:00AM to 21:00PM in every week day except Sunday and
public holidays.

Jobs for them are reserved at 15 minute intervals and whole job must fit to
single day.
Job duration is from 15 minutes to 4 hours.

Reservat table contains reservations, yksus2 table contains workes and
pyha table contains public holidays. Table structures are below. Reservat
structure can changed if this helps.

How to first earliest 30 possible start times considering existing
reservations ?

For example, Mary has already reservation at 12:30 .. 16:00 and
John has already reservation at 12:00 to 13:00

In this case query for job with duration of 1.5 hours should return

    John 2014-10-28 10:00
    Mary 2014-10-28 10:00
    John 2014-10-28 10:30
    Mary 2014-10-28 10:30
    Mary 2014-10-28 11:00
    John 2014-10-28 13:00
    Mary 2014-10-28 16:00
    Mary 2014-10-28 16:30
    ... etc and also starting from next days

I tried query based on answer in
http://stackoverflow.com/questions/13433863/how-to-return-only-work-time-from-reservations-in-postgresql
below but it returns wrong result:

    MARY  2014-10-28 13:00:00
    MARY  2014-10-29 22:34:40.850255
    JOHN  2014-10-30 22:34:40.850255
    MARY  2014-10-31 22:34:40.850255
    MARY  2014-11-03 22:34:40.850255

Also sliding start times 10:00, 10:30 etc are not returned.

How to get proper first reservations ?

Query which I tried is

    insert into reservat (objekt2, during) values
    ('MARY', '[2014-10-28 11:30:00,2014-10-28 13:00:00)'),
    ('JOHN', '[2014-10-28 10:00:00,2014-10-28 11:30:00)');

    with gaps as (
        select
            yksus,
            upper(during) as start,
            lead(lower(during),1,upper(during)) over (ORDER BY during) -
upper(during) as gap
        from (
            select
               yksus2.yksus,
               during
              from reservat join yksus2 on reservat.objekt2=yksus2.yksus
              where  upper(during)>= current_date
            union all
            select
                yksus2.yksus,
                unnest(case
                    when pyha is not null then array[tsrange1(d, d +
interval '1 day')]
                    when date_part('dow', d) in (0, 6) then
array[tsrange1(d, d + interval '1 day')]
                    when d::date =  current_Date then array[
                                tsrange1(d, current_timestamp ),
                                tsrange1(d + interval '20 hours', d +
interval '1 day')]
                    else array[tsrange1(d, d + interval '8 hours'),
                               tsrange1(d + interval '20 hours', d +
interval '1 day')]
                end)
            from yksus2, generate_series(
                current_timestamp,
                current_timestamp + interval '1 month',
                interval '1 day'
            ) as s(d)
            left join pyha on pyha = d::date
        ) as x
    )

    select yksus, start
      from gaps
    where gap >= interval'1hour 30 minutes'
    order by start
    limit 30


Schema:

    CREATE EXTENSION btree_gist;
    CREATE TABLE Reservat (
          id serial primary key,
          objekt2 char(10) not null references yksus2 on update cascade
deferrable,
          during tsrange not null check(
             lower(during)::date = upper(during)::date
             and lower(during) between current_date and current_date+
interval'1 month'

             and (lower(during)::time >= '10:00'::time and
upper(during)::time < '21:00'::time)
             AND EXTRACT(MINUTE FROM lower(during)) IN (0, 15, 30,45)
              AND EXTRACT(MINUTE FROM upper(during)) IN (0, 15, 30, 45)
             and (date_part('dow', lower(during)) in (1,2,3,4,5,6)
             and date_part('dow', upper(during)) in (1,2,3,4,5,6))
          ),

          EXCLUDE USING gist (objekt2 WITH =, during WITH &&)
        );

    create or replace function holiday_check() returns trigger language
plpgsql stable as $$
        begin
            if exists (select * from pyha  where pyha in
(lower(NEW.during)::date, upper(NEW.during)::date)) then
                raise exception 'public holiday %', lower(NEW.during) ;
            else
                return NEW;
            end if;
        end;
        $$;

    create trigger holiday_check_i before insert or update on Reservat for
each row execute procedure holiday_check();

    CREATE OR REPLACE FUNCTION public.tsrange1(start timestamp with time
zone,
        finish timestamp with time zone ) RETURNS tsrange AS
    $BODY$
    SELECT tsrange(start::timestamp without time zone, finish::timestamp
without time zone );
    $BODY$ language sql immutable;


    -- Workers
    create table yksus2( yksus char(10) primary key);
    insert into yksus2 values ('JOHN'), ('MARY');

    -- public holidays
    create table pyha( pyha date primary key);


I posted it also in
http://stackoverflow.com/questions/26608683/how-to-find-first-free-start-times-from-reservations-in-postgres

Andrus.



On 28 October 2014 15:10, Andrus <kobruleht2@hot.ee> wrote:
Hi!

I'm looking for finding ealiest possible start times from reservations table.

People work from 10:00AM to 21:00PM in every week day except Sunday and public holidays.

Jobs for them are reserved at 15 minute intervals and whole job must fit to single day.
Job duration is from 15 minutes to 4 hours.

Reservat table contains reservations, yksus2 table contains workes and
pyha table contains public holidays. Table structures are below. Reservat structure can changed if this helps.

How to first earliest 30 possible start times considering existing reservations ?

For example, Mary has already reservation at 12:30 .. 16:00 and
John has already reservation at 12:00 to 13:00

In this case query for job with duration of 1.5 hours should return

   John 2014-10-28 10:00
   Mary 2014-10-28 10:00
   John 2014-10-28 10:30
   Mary 2014-10-28 10:30
   Mary 2014-10-28 11:00
   John 2014-10-28 13:00
   Mary 2014-10-28 16:00
   Mary 2014-10-28 16:30
   ... etc and also starting from next days

I tried query based on answer in http://stackoverflow.com/questions/13433863/how-to-return-only-work-time-from-reservations-in-postgresql below but it returns wrong result:

   MARY  2014-10-28 13:00:00
   MARY  2014-10-29 22:34:40.850255
   JOHN  2014-10-30 22:34:40.850255
   MARY  2014-10-31 22:34:40.850255
   MARY  2014-11-03 22:34:40.850255

Also sliding start times 10:00, 10:30 etc are not returned.

How to get proper first reservations ?

Query which I tried is

   insert into reservat (objekt2, during) values
   ('MARY', '[2014-10-28 11:30:00,2014-10-28 13:00:00)'),
   ('JOHN', '[2014-10-28 10:00:00,2014-10-28 11:30:00)');

   with gaps as (
       select
           yksus,
           upper(during) as start,
           lead(lower(during),1,upper(during)) over (ORDER BY during) - upper(during) as gap
       from (
           select
              yksus2.yksus,
              during
             from reservat join yksus2 on reservat.objekt2=yksus2.yksus
             where  upper(during)>= current_date
           union all
           select
               yksus2.yksus,
               unnest(case
                   when pyha is not null then array[tsrange1(d, d + interval '1 day')]
                   when date_part('dow', d) in (0, 6) then array[tsrange1(d, d + interval '1 day')]
                   when d::date =  current_Date then array[
                               tsrange1(d, current_timestamp ),
                               tsrange1(d + interval '20 hours', d + interval '1 day')]
                   else array[tsrange1(d, d + interval '8 hours'),
                              tsrange1(d + interval '20 hours', d + interval '1 day')]
               end)
           from yksus2, generate_series(
               current_timestamp,
               current_timestamp + interval '1 month',
               interval '1 day'
           ) as s(d)
           left join pyha on pyha = d::date
       ) as x
   )

   select yksus, start
     from gaps
   where gap >= interval'1hour 30 minutes'
   order by start
   limit 30


Schema:

   CREATE EXTENSION btree_gist;
   CREATE TABLE Reservat (
         id serial primary key,
         objekt2 char(10) not null references yksus2 on update cascade deferrable,
         during tsrange not null check(
            lower(during)::date = upper(during)::date
            and lower(during) between current_date and current_date+ interval'1 month'

            and (lower(during)::time >= '10:00'::time and upper(during)::time < '21:00'::time)
            AND EXTRACT(MINUTE FROM lower(during)) IN (0, 15, 30,45)
             AND EXTRACT(MINUTE FROM upper(during)) IN (0, 15, 30, 45)
            and (date_part('dow', lower(during)) in (1,2,3,4,5,6)
            and date_part('dow', upper(during)) in (1,2,3,4,5,6))
         ),

         EXCLUDE USING gist (objekt2 WITH =, during WITH &&)
       );

   create or replace function holiday_check() returns trigger language plpgsql stable as $$
       begin
           if exists (select * from pyha  where pyha in (lower(NEW.during)::date, upper(NEW.during)::date)) then
               raise exception 'public holiday %', lower(NEW.during) ;
           else
               return NEW;
           end if;
       end;
       $$;

   create trigger holiday_check_i before insert or update on Reservat for each row execute procedure holiday_check();

   CREATE OR REPLACE FUNCTION public.tsrange1(start timestamp with time zone,
       finish timestamp with time zone ) RETURNS tsrange AS
   $BODY$
   SELECT tsrange(start::timestamp without time zone, finish::timestamp without time zone );
   $BODY$ language sql immutable;


   -- Workers
   create table yksus2( yksus char(10) primary key);
   insert into yksus2 values ('JOHN'), ('MARY');

   -- public holidays
   create table pyha( pyha date primary key);


I posted it also in http://stackoverflow.com/questions/26608683/how-to-find-first-free-start-times-from-reservations-in-postgres

Andrus. 

Would you be able to adapt this to your needs?:

CREATE TABLE yksus2 (yksus char(10) PRIMARY KEY);
INSERT INTO yksus2 VALUES ('JOHN'),('MARY');

CREATE TABLE reservat
(
id serial primary key,
objekt2 char(10) REFERENCES yksus2 (yksus),
during tstzrange
);

ALTER TABLE reservat ADD CONSTRAINT time_between_1000_and_2100
CHECK (lower(during) >= (lower(during)::date + '10:00'::time)::timestamptz
AND upper(during) < (upper(during)::date + '21:00+1'::time)::timestamptz);

ALTER TABLE reservat ADD CONSTRAINT time_at_15_min_offset
CHECK (extract(epoch from lower(during)::time)::int % (60*15) = 0);

ALTER TABLE reservat ADD CONSTRAINT duration_between_15min_and_4hours
CHECK (upper(during) - lower(during) between '15 mins'::interval and '4 hours'::interval);

INSERT INTO reservat (objekt2, during)
  VALUES ('MARY','[2014-10-28 12:30+0,2014-10-28 16:00+0)'::tstzrange);
INSERT INTO reservat (objekt2, during)
  VALUES ('JOHN','[2014-10-28 12:00+0,2014-10-28 13:00+0)'::tstzrange);

SELECT yksus2.yksus, times.period
FROM generate_series('2014-10-28 10:00+0'::timestamptz, '2014-10-28 21:00+0', '15 mins'::interval) times(period)
CROSS JOIN yksus2
LEFT JOIN reservat ON tstzrange(times.period,times.period + '1 hour 30 mins'::interval, '[)') && reservat.during AND yksus2.yksus = reservat.objekt2
WHERE reservat.during IS NULL
ORDER BY 2, 1
LIMIT 30;

   yksus    |         period         
------------+------------------------
 JOHN       | 2014-10-28 10:00:00+00
 MARY       | 2014-10-28 10:00:00+00
 JOHN       | 2014-10-28 10:15:00+00
 MARY       | 2014-10-28 10:15:00+00
 JOHN       | 2014-10-28 10:30:00+00
 MARY       | 2014-10-28 10:30:00+00
 MARY       | 2014-10-28 10:45:00+00
 MARY       | 2014-10-28 11:00:00+00
 JOHN       | 2014-10-28 13:00:00+00
 JOHN       | 2014-10-28 13:15:00+00
 JOHN       | 2014-10-28 13:30:00+00
 JOHN       | 2014-10-28 13:45:00+00
 JOHN       | 2014-10-28 14:00:00+00
 JOHN       | 2014-10-28 14:15:00+00
 JOHN       | 2014-10-28 14:30:00+00
 JOHN       | 2014-10-28 14:45:00+00
 JOHN       | 2014-10-28 15:00:00+00
 JOHN       | 2014-10-28 15:15:00+00
 JOHN       | 2014-10-28 15:30:00+00
 JOHN       | 2014-10-28 15:45:00+00
 JOHN       | 2014-10-28 16:00:00+00
 MARY       | 2014-10-28 16:00:00+00
 JOHN       | 2014-10-28 16:15:00+00
 MARY       | 2014-10-28 16:15:00+00
 JOHN       | 2014-10-28 16:30:00+00
 MARY       | 2014-10-28 16:30:00+00
 JOHN       | 2014-10-28 16:45:00+00
 MARY       | 2014-10-28 16:45:00+00
 JOHN       | 2014-10-28 17:00:00+00
 MARY       | 2014-10-28 17:00:00+00
(30 rows)

-- 
Thom
Hi!
 
>Would you be able to adapt this to your needs?:
 
Thank you very much.
Great solution.
I refactored it as shown below.
Query returns only dates for single day. Changing limit clause to 300 does not return next day.
How to return other day dates also, excluding sundays and public holidays in pyha table ?
 
Andrus.
 
Testcase is:
 
create table pyha (pyha date primary key);
insert into pyha(pyha) values('2014-10-29');
create table  yksus2(yksus char(10) primary key);
insert into yksus2 values ('JOHN'),('MARY');
CREATE EXTENSION btree_gist;
 
CREATE TABLE reservat
(
  reservat_id serial primary key,
      objekt2 char(10) not null references yksus2 on update cascade deferrable,
during tstzrange not null,
EXCLUDE USING gist (objekt2 WITH =, during WITH &&),
 
CONSTRAINT same_date
     CHECK (lower(during)::date = upper(during)::date),
 
CONSTRAINT max_1month_future
     CHECK (lower(during) between current_date and current_date+ interval'1 month' ),
 
CONSTRAINT time_between_1000_and_2100
     CHECK (lower(during)::time >= '10:00'::time and upper(during)::time < '21:00'::time),
 
CONSTRAINT lower_bound_included
     CHECK (lower_inc(during)),
 
CONSTRAINT upper_bound_excluded
     CHECK (not upper_inc(during)),
 
CONSTRAINT start_time_at_15minute_offset
     CHECK (EXTRACT(MINUTE FROM lower(during)) IN (0, 15, 30,45)),
    -- or (extract(epoch from lower(during)::time)::int % (60*15) = 0)
 
CONSTRAINT end_time_at_15minute_offset
     CHECK (EXTRACT(MINUTE FROM upper(during)) IN (0, 15, 30,45)),
 
CONSTRAINT duration_between_15min_and_4hours
     CHECK (upper(during) - lower(during) between '15 mins'::interval and '4 hours'::interval),
 
CONSTRAINT exclude_sundays
     CHECK (date_part('dow', lower(during)) in (1,2,3,4,5,6) )
);
 
create or replace function holiday_check() returns trigger language plpgsql stable as $$
    begin
        if exists (select * from pyha  where pyha between lower(NEW.during)::date and upper(NEW.during)::date) then
            raise exception 'public holiday %', lower(NEW.during) ;
        else
            return NEW;
        end if;
    end;
    $$;
 
create trigger holiday_check_i before insert or update on Reservat for each row execute procedure holiday_check();
INSERT INTO reservat (objekt2, during)
  VALUES ('MARY','[2014-10-28 11:30+2,2014-10-28 13:00+2)'::tstzrange);
INSERT INTO reservat (objekt2, during)
  VALUES ('JOHN','[2014-10-28 10:00+2,2014-10-28 11:30+2)'::tstzrange);
 
SELECT yksus2.yksus, times.period
FROM generate_series('2014-10-28 10:00+2'::timestamptz, '2014-10-28 21:00+2', '15 mins'::interval) times(period)
CROSS JOIN yksus2
LEFT JOIN reservat ON tstzrange(times.period,times.period + '1 hour 30 mins'::interval, '[)') && reservat.during AND yksus2.yksus = reservat.objekt2
WHERE reservat.during IS NULL
ORDER BY 2, 1
LIMIT 300;
On 28 October 2014 19:14, Andrus <kobruleht2@hot.ee> wrote:
Hi!
 
>Would you be able to adapt this to your needs?:
 
Thank you very much.
Great solution.
I refactored it as shown below.
Query returns only dates for single day. Changing limit clause to 300 does not return next day.
How to return other day dates also, excluding sundays and public holidays in pyha table ?

It's not a robust solution if you need it to span days, but you could just increment the 2nd timestamptz parameter in the generate_series function call by a year:

generate_series('2014-10-28 10:00+2'::timestamptz, '2015-10-28 21:00+2', '15 mins'::interval)

It's hacky, but it should work, but if you happened to have a policy whereby reservations couldn't be made beyond, say, 3 months in advance, you could just give it a date 3 months in the future, and make sure that the first parameter is capped to the same range.

So here's an example of what you could do (although it could probably be simplified and made more elegant).  Here it will find times from the current time until 3 months in the future.  It also filters out holiday dates.

SELECT yksus2.yksus, times.period
FROM generate_series(now()::date::timestamptz, now()::date::timestamptz + '3 months'::interval, '15 mins'::interval) times(period)
CROSS JOIN yksus2
LEFT JOIN reservat ON tstzrange(times.period,times.period + '1 hour 30 mins'::interval, '[)') && reservat.during
  AND yksus2.yksus = reservat.objekt2
LEFT JOIN pyha ON times.period::date = pyha.pyha::date
WHERE reservat.during IS NULL
  AND pyha.pyha IS NULL
  AND times.period::time BETWEEN '10:00'::time AND '21:00'::time
  AND times.period >= now()
ORDER BY 2, 1
LIMIT 300;

--
Thom
On 28 October 2014 20:04, Thom Brown <thom@linux.com> wrote:
On 28 October 2014 19:14, Andrus <kobruleht2@hot.ee> wrote:
Hi!
 
>Would you be able to adapt this to your needs?:
 
Thank you very much.
Great solution.
I refactored it as shown below.
Query returns only dates for single day. Changing limit clause to 300 does not return next day.
How to return other day dates also, excluding sundays and public holidays in pyha table ?

It's not a robust solution if you need it to span days, but you could just increment the 2nd timestamptz parameter in the generate_series function call by a year:

generate_series('2014-10-28 10:00+2'::timestamptz, '2015-10-28 21:00+2', '15 mins'::interval)

It's hacky, but it should work, but if you happened to have a policy whereby reservations couldn't be made beyond, say, 3 months in advance, you could just give it a date 3 months in the future, and make sure that the first parameter is capped to the same range.

So here's an example of what you could do (although it could probably be simplified and made more elegant).  Here it will find times from the current time until 3 months in the future.  It also filters out holiday dates.

SELECT yksus2.yksus, times.period
FROM generate_series(now()::date::timestamptz, now()::date::timestamptz + '3 months'::interval, '15 mins'::interval) times(period)
CROSS JOIN yksus2
LEFT JOIN reservat ON tstzrange(times.period,times.period + '1 hour 30 mins'::interval, '[)') && reservat.during
  AND yksus2.yksus = reservat.objekt2
LEFT JOIN pyha ON times.period::date = pyha.pyha::date
WHERE reservat.during IS NULL
  AND pyha.pyha IS NULL
  AND times.period::time BETWEEN '10:00'::time AND '21:00'::time
  AND times.period >= now()
ORDER BY 2, 1
LIMIT 300;

A correction to this.  As it stands, it will show times like the following:

   yksus    |         period         
------------+------------------------
...
 JOHN       | 2014-10-30 19:45:00+00
 MARY       | 2014-10-30 19:45:00+00
 JOHN       | 2014-10-30 20:00:00+00
 MARY       | 2014-10-30 20:00:00+00
 JOHN       | 2014-10-30 20:15:00+00
 MARY       | 2014-10-30 20:15:00+00
 JOHN       | 2014-10-30 20:30:00+00
 MARY       | 2014-10-30 20:30:00+00
 JOHN       | 2014-10-30 20:45:00+00
 MARY       | 2014-10-30 20:45:00+00
 JOHN       | 2014-10-30 21:00:00+00
 MARY       | 2014-10-30 21:00:00+00
 JOHN       | 2014-10-31 10:00:00+00
 MARY       | 2014-10-31 10:00:00+00
...

This is incorrect a 1.5 hour appointment after 19:30 would go beyond the working hours.  So that needs to be factored into it:

SELECT yksus2.yksus, times.period
FROM generate_series(now()::date::timestamptz, now()::date::timestamptz + '3 months'::interval, '15 mins'::interval) times(period)
CROSS JOIN yksus2
LEFT JOIN reservat ON tstzrange(times.period,times.period + '1 hour 30 mins'::interval, '[)') && reservat.during
  AND yksus2.yksus = reservat.objekt2
LEFT JOIN pyha ON times.period::date = pyha.pyha::date
WHERE reservat.during IS NULL
  AND pyha.pyha IS NULL
  AND times.period::timetz BETWEEN '10:00'::timetz AND '21:00'::timetz - '1 hour 30 mins'::interval
  AND times.period >= now()
ORDER BY 2, 1
LIMIT 300;

This gives you:

   yksus    |         period         
------------+------------------------
...
 JOHN       | 2014-10-30 19:15:00+00
 MARY       | 2014-10-30 19:15:00+00
 JOHN       | 2014-10-30 19:30:00+00
 MARY       | 2014-10-30 19:30:00+00
 JOHN       | 2014-10-31 10:00:00+00
 MARY       | 2014-10-31 10:00:00+00
 JOHN       | 2014-10-31 10:15:00+00
 MARY       | 2014-10-31 10:15:00+00
...

Regards

Thom
Hi!
 
>A correction to this.  As it stands, it will show times like the following:
 
Thank you.
I posted your solution as alternative to Erwin answer in
 
Andrus.
 
On 28 October 2014 21:07, Andrus <kobruleht2@hot.ee> wrote:
Hi!
 
>A correction to this.  As it stands, it will show times like the following:
 
Thank you.
I posted your solution as alternative to Erwin answer in
 

A further tweak; add the following to the WHERE clause:

AND EXTRACT(DOW FROM times.period) != 0

This will ensure Sundays are excluded.  I don't know if you want Saturdays excluded, but you can easily adjust it for that.
 
Thom
Hi!

>A further tweak; add the following to the WHERE clause:
>AND EXTRACT(DOW FROM times.period) != 0

I changed it to isodow to work in any locale.

Your solution is more readable but Erwin answer in SO looks more optimized.
I have 10 workes and 1 month reservation with 15 minute offsess from 8 to
20:00, so perfomance is hopafully not an issue. Which to use ?

Using current_date in check constraint causes database restore failure.
not valid should be added or this check should be moved to holydays check
trigger.

Andrus.