Обсуждение: Finding gaps in scheduled events
Hello.
I've been struggling with this one for over a week, but for some reason my
mind isn't compatibile with the problem - it seems simple, yet I'm unable
to find the proper solution :(.
I have a timeline divided to 15 minute periods:
start |
------+8:00 | 8:15 |8:30 |8:45 |(...)|
14:45 |
Then, I have two types of events that fit the schedule. Event A takes
15 minutes, event B takes 30 minutes. They're stored in a table like this:
start | finish | type_id
------+--------+--------
8:30 | 8:45 | 1 -> type A
9:30 | 10:00 | 2 -> type B
Now I need to create a query to find hours at which each of the type can
start. So, if it's event A (which take 15 minutes) it can start at:
8:00 (to 8:15)
8:15 (to 8:30)
( 8:30 to 8:45 is already taken )
8:45 (to 9:00)
9:00 (to 9:15)
9:15 (to 9:30)
( 9:30 to 10:00 (9:30-9:45 and 9:45-10:00) is already taken))
10:00 (to 10:15)
(...)
and if it's event B (which takes 30 minutes) it can start at:
8:00 (to 8:30)
8:45 (to 9:15)
9:00 (to 9:30)
10:00 (to 10:30)
(...)
I have to deal with the existing schema, but if it can be done in a
better way please let me know so I could avoid mistakes in my own programs
(although I think it's quite flexible and I like the concept).
Example tables:
create table test_events ( id serial, start time, finish time, type_id integer );
insert into test_events ( start,finish,type_id ) values('8:30','8:45','1');
insert into test_events ( start,finish,type_id ) values ('9:30','10:00','2');
create table test_timeline as SELECT ('0:00'::TIME + (my_day.h || ' minutes')::INTERVAL)::TIME as my_hour
FROM generate_series (0,1425,15) AS my_day(h);
I don't paste my tries because they've all failed and I think I miss
something fundamental here.
Thank you very much for your time.
--
| And Do What You Will be the challenge | http://apcoln.linuxpl.org
| So be it in love that harms none | http://biznes.linux.pl
| For this is the only commandment. | http://www.juanperon.info
`---* JID: Aragorn_Vime@jabber.org *---' http://www.naszedzieci.org
Marcin Stępnicki wrote: > > start | finish | type_id > ------+--------+-------- > 8:30 | 8:45 | 1 -> type A > 9:30 | 10:00 | 2 -> type B > I have to deal with the existing schema, but if it can be done in a > better way please let me know so I could avoid mistakes in my own programs > (although I think it's quite flexible and I like the concept). The reason you're finding it difficult is that you're asking the database for information based on what *isn't* stored in it. That is you're asking it for all the gaps in your event data. Now, if you were doing it by hand you'd sort the events according to time and compare finish/start times in order. You can do something similar with PG and write a plpgsql function that returns a setof (start,finish,length) for gaps. If you have a lot of events and you need to find gaps quite often it might be easier to keep a separate table to track them. Triggers on the events table would keep the gaps table up to date. If events can be deleted/moved you'll want to consider how to merge adjacent gaps. If you don't like either of those, you'll need to figure out what the "next" and "previous" events are for each event in your table. That will need to be a sub-query with something like: SELECT a.start, a.finish, ( SELECT start FROM test_events WHERE start>a.finish ORDER BY start LIMIT 1 ) AS next_start FROM test_events a ORDER BY start; Note the subquery is in the SELECT clause and this query-plan will probably run over the table twice (via indexes). HTH -- Richard Huxton Archonet Ltd
Richard Huxton wrote: > Marcin Stępnicki wrote: >> >> start | finish | type_id >> ------+--------+-------- >> 8:30 | 8:45 | 1 -> type A >> 9:30 | 10:00 | 2 -> type B > >> I have to deal with the existing schema, but if it can be done in a >> better way please let me know so I could avoid mistakes in my own >> programs >> (although I think it's quite flexible and I like the concept). > > The reason you're finding it difficult is that you're asking the > database for information based on what *isn't* stored in it. That is > you're asking it for all the gaps in your event data. > > Now, if you were doing it by hand you'd sort the events according to > time and compare finish/start times in order. You can do something > similar with PG and write a plpgsql function that returns a setof > (start,finish,length) for gaps. You wouldn't even need the sort. In the function just loop, starting at the earliest possible event start time, and increment by 15 minutes until you've hit the last possible start time and at each time check to see if there is already an event scheduled for that time, if there was a 30 minute event that is scheduled to start 15 minutes earlier, or if there is an event already scheduled to start at the next time (which would limit an event at the current time to 15 minutes). You could make it "smarter" by observing that whenever you get to an event that's 30 minutes long you can skip checking the next start time. > If you have a lot of events and you need to find gaps quite often it > might be easier to keep a separate table to track them. Triggers on > the events table would keep the gaps table up to date. If events can > be deleted/moved you'll want to consider how to merge adjacent gaps. Also a good idea. > > If you don't like either of those, you'll need to figure out what the > "next" and "previous" events are for each event in your table. That > will need to be a sub-query with something like: > > SELECT > a.start, > a.finish, > ( > SELECT start FROM test_events WHERE start>a.finish ORDER BY start > LIMIT 1 > ) AS next_start > FROM > test_events a > ORDER BY start; > > Note the subquery is in the SELECT clause and this query-plan will > probably run over the table twice (via indexes). Here your still left mostly in the dark and still need to loop through the results checking the gaps between a.finish and next start. And, since you're working with the full result set at that point and it is already ordered by each event's start time, you don't need the subquery as at each iteration of the loop you can do a simple difference of the current row's a.finish and the next's a.start to get the gap (with a special case to handle the last scheduled event). -- erik jones <erik@myemma.com> software development emma(r)
Marcin Stępnicki wrote: > Now I need to create a query to find hours at which each of the type can > start. So, if it's event A (which take 15 minutes) it can start at: > > 8:00 (to 8:15) > 8:15 (to 8:30) > ( 8:30 to 8:45 is already taken ) > 8:45 (to 9:00) > 9:00 (to 9:15) > 9:15 (to 9:30) > ( 9:30 to 10:00 (9:30-9:45 and 9:45-10:00) is already taken)) > 10:00 (to 10:15) I think something like this should help you: select my_hour from test_events right join test_timeline on ((start, finish) overlaps (my_hour, my_hour + 15 * '1 minute'::interval)) where start is null; With your test data, it shows all the times except for 8:30, 9:30 and 9:45.
Alvaro Herrera wrote: > Marcin Stępnicki wrote: > > >> Now I need to create a query to find hours at which each of the type can >> start. So, if it's event A (which take 15 minutes) it can start at: >> >> 8:00 (to 8:15) >> 8:15 (to 8:30) >> ( 8:30 to 8:45 is already taken ) >> 8:45 (to 9:00) >> 9:00 (to 9:15) >> 9:15 (to 9:30) >> ( 9:30 to 10:00 (9:30-9:45 and 9:45-10:00) is already taken)) >> 10:00 (to 10:15) >> > > I think something like this should help you: > > select my_hour > from test_events right join test_timeline on > ((start, finish) overlaps (my_hour, my_hour + 15 * '1 minute'::interval)) > where start is null; > > With your test data, it shows all the times except for 8:30, 9:30 and > 9:45. > Nice! And, he can run that query again, flipping the 15 to 30, to get the list of available 30 minute gaps. That's a heck-of-a lot simpler than the stuff I discussed earlier. -- erik jones <erik@myemma.com> software development emma(r)