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(at)jabber(dot)org *---' http://www.naszedzieci.org