1 Reply Latest reply on Dec 17, 2008 11:00 PM by Rob van Wijk

    fill in the gaps in the schedule

    Ronald Rood
      I guess this is something for a nice piece of an analytical sql. Can this be done in 1 sql Rob?

      I have a table that contains a list of items that are to be discussed in a meeting, all taking place in the same room. For some meetings a guest speaker is invited, those meetings have a fixed start time. All meetings have a fixed duration in minutes. The days all start with opening and end with close. How can we generate the start times of the items that have no fixed start time set?

      input data is as follows:

      create table sschedule (
      item varchar2(10)
      , days varchar2(30)
      , fixed_start_time varchar2(5)
      , minutes number
      );

      insert into sschedule (item,days, fixed_start_time, minutes) values ('lunch', 'mon,tue,wed,thu,fri','12:00',60);
      insert into sschedule (item,days, fixed_start_time, minutes) values ('a', 'tue,fri','10:00',60);
      insert into sschedule (item,days, fixed_start_time, minutes) values ('b', 'mon,wed',null, 120);
      insert into sschedule (item,days, fixed_start_time, minutes) values ('opening','mon,tue,wed,thu,fri','08:55', 5);
      insert into sschedule (item,days, fixed_start_time, minutes) values ('close','mon,tue,wed,thu','20:00', 5);
      insert into sschedule (item,days, fixed_start_time, minutes) values ('close','fri','16:00', 5);
      insert into sschedule (item,days, fixed_start_time, minutes) values ('c', 'mon,wed,fri',null, 20);
      insert into sschedule (item,days, fixed_start_time, minutes) values ('d', 'mon,wed,fri',null, 20);
      insert into sschedule (item,days, fixed_start_time, minutes) values ('diner','mon,tue,wed,thu','18:00', 60);
      insert into sschedule (item,days, fixed_start_time, minutes) values ('e','tue,thu,fri',null, 40);
      insert into sschedule (item,days, fixed_start_time, minutes) values ('keynote', 'mon','09:00', 120);
      insert into sschedule (item,days, fixed_start_time, minutes) values ('bye', 'fri','14:00', 120);
      insert into sschedule (item,days, fixed_start_time, minutes) values ('f','tue,thu,fri',null, 40);
      insert into sschedule (item,days, fixed_start_time, minutes) values ('g', 'mon,wed',null, 120);

      for friday this gives:
      ITEM     FIXED MINUTES
      ---------- ----- ----------
      opening 08:55     5
      a     10:00     60
      lunch     12:00     60
      bye     14:00     120
      close     16:00     5
      c               20
      d               20
      e               40
      f               40

      e can start at 09:00 to fill the gap between opening and a.
      c can start at 09:40 to fill the gap between e and a.
      f can start at 11:00 to fill the gap between a and lunch.
      d can start at 11:40 to fill the gap between f and lunch.

      more combinations are very legal, as long as the fixed_start_times are honoured.
      How can this list be generated in 1 sql?
      When a day becomes overbooked the items that fall must get something like 'does not fit' to signal it's too busy that day.

      thanks,
      Ronald.
        • 1. Re: fill in the gaps in the schedule
          Rob van Wijk
          Ronald Rood wrote:
          Can this be done in 1 sql Rob?
          Of course, Ronald ;-)

          You didn't describe what algorithm to use, so I used a quite simple one. It justs assigns items to the beginning of open time slots, the largest ones first, assigned to the largest gaps first.
          SQL> with schedule_normalized as
            2  ( select item
            3         , cast(days as varchar2(3)) day
            4         , to_date(fixed_start_time,'hh24:mi') start_time
            5         , minutes
            6         , to_date(fixed_start_time,'hh24:mi')
            7           + numtodsinterval(minutes,'minute') end_time
            8      from sschedule
            9     model
           10           return updated rows
           11           partition by (item,fixed_start_time,minutes)
           12           dimension by (0 i)
           13           measures (days)
           14           ( days [for i from 1 to regexp_count(days[0],',') + 1 increment 1]
           15             = regexp_substr(days[0],'[^,]+',1,cv(i))
           16           )
           17  )
           18  select item
           19       , day
           20       , to_char(st,'hh24:mi') start_time
           21       , to_char(et,'hh24:mi') end_time
           22       , minutes
           23       , fit
           24    from schedule_normalized
           25   model
           26         partition by (day)
           27         dimension by
           28         ( row_number() over
           29           (partition by day order by start_time nulls first, minutes desc) rn
           30         )
           31         measures
           32         ( item
           33         , start_time st
           34         , minutes
           35         , end_time et
           36         , lead(start_time) over
           37           (partition by day order by start_time) next_start_time
           38         , count(nvl2(start_time,null,1)) over (partition by day) cnt
           39         , 0 rn_with_largest_gap
           40         , row_number() over
           41           (partition by day order by start_time nulls first, minutes desc) rnm
           42         , cast(null as varchar2(11)) fit
           43         )
           44         rules iterate(1000) until (iteration_number + 1 = cnt[1])
           45         ( rn_with_largest_gap[1]
           46           = max(rnm) keep
           47             (dense_rank last order by next_start_time - et nulls first)[any]
           48         , fit[iteration_number+1]
           49           = case
           50               when max(next_start_time - et)[any]
           51                  < minutes[iteration_number+1]/24/60
           52               then 'doesn''t fit'
           53             end
           54         , st[iteration_number+1]
           55           = case
           56               when fit[iteration_number+1] is null
           57               then et[rn_with_largest_gap[1]]
           58             end
           59         , et[iteration_number+1]
           60           = case
           61               when fit[iteration_number+1] is null
           62               then et[rn_with_largest_gap[1]]
           63                    + numtodsinterval(minutes[iteration_number+1],'minute')
           64             end
           65         , next_start_time[iteration_number+1]
           66           = case
           67               when fit[iteration_number+1] is null
           68               then next_start_time[rn_with_largest_gap[1]]
           69             end
           70         , next_start_time[rn_with_largest_gap[1]]
           71           = case
           72               when fit[iteration_number+1] is not null
           73               then next_start_time[rn_with_largest_gap[1]]
           74             end
           75         )
           76   order by decode(day,'mon',1,'tue',2,'wed',3,'thu',4,'fri',5)
           77       , start_time
           78  /
          
          ITEM       DAY START END_T    MINUTES FIT
          ---------- --- ----- ----- ---------- -----------
          opening    mon 08:55 09:00          5
          keynote    mon 09:00 11:00        120
          d          mon 11:00 11:20         20
          lunch      mon 12:00 13:00         60
          g          mon 13:00 15:00        120
          b          mon 15:00 17:00        120
          diner      mon 18:00 19:00         60
          c          mon 19:00 19:20         20
          close      mon 20:00 20:05          5
          opening    tue 08:55 09:00          5
          a          tue 10:00 11:00         60
          lunch      tue 12:00 13:00         60
          f          tue 13:00 13:40         40
          e          tue 13:40 14:20         40
          diner      tue 18:00 19:00         60
          close      tue 20:00 20:05          5
          opening    wed 08:55 09:00          5
          g          wed 09:00 11:00        120
          lunch      wed 12:00 13:00         60
          b          wed 13:00 15:00        120
          d          wed 15:00 15:20         20
          c          wed 15:20 15:40         20
          diner      wed 18:00 19:00         60
          close      wed 20:00 20:05          5
          opening    thu 08:55 09:00          5
          lunch      thu 12:00 13:00         60
          e          thu 13:00 13:40         40
          f          thu 13:40 14:20         40
          diner      thu 18:00 19:00         60
          close      thu 20:00 20:05          5
          opening    fri 08:55 09:00          5
          d          fri 09:00 09:20         20
          c          fri 09:20 09:40         20
          a          fri 10:00 11:00         60
          f          fri 11:00 11:40         40
          lunch      fri 12:00 13:00         60
          e          fri 13:00 13:40         40
          bye        fri 14:00 16:00        120
          close      fri 16:00 16:05          5
          
          39 rijen zijn geselecteerd.
          And an example with items that don't fit:
          SQL> insert into sschedule (item,days, fixed_start_time, minutes) values ('z', 'mon',null, 240);
          
          1 rij is aangemaakt.
          
          SQL> with schedule_normalized as
            2  ( select item
            3         , cast(days as varchar2(3)) day
            4         , to_date(fixed_start_time,'hh24:mi') start_time
            5         , minutes
            6         , to_date(fixed_start_time,'hh24:mi')
            7           + numtodsinterval(minutes,'minute') end_time
            8      from sschedule
            9     model
           10           return updated rows
           11           partition by (item,fixed_start_time,minutes)
           12           dimension by (0 i)
           13           measures (days)
           14           ( days [for i from 1 to regexp_count(days[0],',') + 1 increment 1]
           15             = regexp_substr(days[0],'[^,]+',1,cv(i))
           16           )
           17  )
           18  select item
           19       , day
           20       , to_char(st,'hh24:mi') start_time
           21       , to_char(et,'hh24:mi') end_time
           22       , minutes
           23       , fit
           24    from schedule_normalized
           25   model
           26         partition by (day)
           27         dimension by
           28         ( row_number() over
           29           (partition by day order by start_time nulls first, minutes desc) rn
           30         )
           31         measures
           32         ( item
           33         , start_time st
           34         , minutes
           35         , end_time et
           36         , lead(start_time) over
           37           (partition by day order by start_time) next_start_time
           38         , count(nvl2(start_time,null,1)) over (partition by day) cnt
           39         , 0 rn_with_largest_gap
           40         , row_number() over
           41           (partition by day order by start_time nulls first, minutes desc) rnm
           42         , cast(null as varchar2(11)) fit
           43         )
           44         rules iterate(1000) until (iteration_number + 1 = cnt[1])
           45         ( rn_with_largest_gap[1]
           46           = max(rnm) keep
           47             (dense_rank last order by next_start_time - et nulls first)[any]
           48         , fit[iteration_number+1]
           49           = case
           50               when max(next_start_time - et)[any]
           51                  < minutes[iteration_number+1]/24/60
           52               then 'doesn''t fit'
           53             end
           54         , st[iteration_number+1]
           55           = case
           56               when fit[iteration_number+1] is null
           57               then et[rn_with_largest_gap[1]]
           58             end
           59         , et[iteration_number+1]
           60           = case
           61               when fit[iteration_number+1] is null
           62               then et[rn_with_largest_gap[1]]
           63                    + numtodsinterval(minutes[iteration_number+1],'minute')
           64             end
           65         , next_start_time[iteration_number+1]
           66           = case
           67               when fit[iteration_number+1] is null
           68               then next_start_time[rn_with_largest_gap[1]]
           69             end
           70         , next_start_time[rn_with_largest_gap[1]]
           71           = case
           72               when fit[iteration_number+1] is not null
           73               then next_start_time[rn_with_largest_gap[1]]
           74             end
           75         )
           76   order by decode(day,'mon',1,'tue',2,'wed',3,'thu',4,'fri',5)
           77       , start_time
           78  /
          
          ITEM       DAY START END_T    MINUTES FIT
          ---------- --- ----- ----- ---------- -----------
          opening    mon 08:55 09:00          5
          keynote    mon 09:00 11:00        120
          c          mon 11:00 11:20         20
          lunch      mon 12:00 13:00         60
          z          mon 13:00 17:00        240
          diner      mon 18:00 19:00         60
          d          mon 19:00 19:20         20
          close      mon 20:00 20:05          5
          b          mon                    120 doesn't fit
          g          mon                    120 doesn't fit
          opening    tue 08:55 09:00          5
          a          tue 10:00 11:00         60
          lunch      tue 12:00 13:00         60
          e          tue 13:00 13:40         40
          f          tue 13:40 14:20         40
          diner      tue 18:00 19:00         60
          close      tue 20:00 20:05          5
          opening    wed 08:55 09:00          5
          b          wed 09:00 11:00        120
          lunch      wed 12:00 13:00         60
          g          wed 13:00 15:00        120
          c          wed 15:00 15:20         20
          d          wed 15:20 15:40         20
          diner      wed 18:00 19:00         60
          close      wed 20:00 20:05          5
          opening    thu 08:55 09:00          5
          lunch      thu 12:00 13:00         60
          e          thu 13:00 13:40         40
          f          thu 13:40 14:20         40
          diner      thu 18:00 19:00         60
          close      thu 20:00 20:05          5
          opening    fri 08:55 09:00          5
          c          fri 09:00 09:20         20
          d          fri 09:20 09:40         20
          a          fri 10:00 11:00         60
          f          fri 11:00 11:40         40
          lunch      fri 12:00 13:00         60
          e          fri 13:00 13:40         40
          bye        fri 14:00 16:00        120
          close      fri 16:00 16:05          5
          
          40 rijen zijn geselecteerd.
          Groet,
          Rob.

          Edited by: Rob van Wijk on 17-dec-2008 23:59

          Removed unnecessary measure x