Minimum number of Meeting Rooms required to Accomodate all Meetings in MySQL

Question

I have the following columns in a table called meetings: meeting_id - int, start_time - time, end_time - time. Assuming that this table has data for one calendar day only, how many minimum number of rooms do I need to accomodate all the meetings. Room size/number of people attending the meetings don't matter.

Here's the solution:

select * from
(select t.start_time, 
        t.end_time, 
        count(*) - 1 overlapping_meetings, 
        count(*) minimum_rooms_required,
        group_concat(distinct concat(y.start_time,' to ',t.end_time) 
separator ' // ') meeting_details from 
(select 1 meeting_id, '08:00' start_time, '09:15' end_time union all
select 2, '13:20', '15:20' union all
select 3, '10:00', '14:00' union all
select 4, '13:55', '16:25' union all
select 5, '14:00', '17:45' union all
select 6, '14:05', '17:45') t left join 

(select 1 meeting_id, '08:00' start_time, '09:15' end_time union all
select 2, '13:20', '15:20' union all
select 3, '10:00', '14:00' union all
select 4, '13:55', '16:25' union all
select 5, '14:00', '17:45' union all
select 6, '14:05', '17:45') y

on t.start_time between y.start_time and y.end_time

group by start_time, end_time) z;

My question - is there anything wrong with this answer? Even if there's nothing wrong with this, can someone share a better answer?

Answer 1

Let's say you have a table called 'meeting' like this -

Then You can use this query to get the minimum number of meeting Rooms required to accommodate all Meetings.

select max(minimum_rooms_required)
from (select count(*) minimum_rooms_required
      from meetings t
      left join meetings y on t.start_time >= y.start_time and t.start_time < y.end_time group by t.id
) z;

This looks clearer and simple and works fine.

Answer 2

Meetings can "overlap". So, GROUP BY start_time, end_time can't figure this out.

Not every algorithm can be done in SQL. Or, at least, it may be grossly inefficient.

I would use a real programming language for the computation, leaving the database for what it is good at -- being a data repository.

Build a array of 1440 (minutes in a day) entries; initialize to 0.
Foreach meeting:
    Foreach minute in the meeting (excluding last minute):
        increment element in array.
Find the largest element in the array -- the number of rooms needed.

Answer 3

CREATE TABLE [dbo].[Meetings](
[id] [int] NOT NULL,
[Starttime] [time](7) NOT NULL,
[EndTime] [time](7) NOT NULL) ON [PRIMARY] )GO

sample data set:

INSERT INTO Meetings VALUES (1,'8:00','09:00')
INSERT INTO Meetings VALUES (2,'8:00','10:00')
INSERT INTO Meetings VALUES (3,'10:00','11:00')
INSERT INTO Meetings VALUES (4,'11:00','12:00')
INSERT INTO Meetings VALUES (5,'11:00','13:00')
INSERT INTO Meetings VALUES (6,'13:00','14:00')
INSERT INTO Meetings VALUES (7,'13:00','15:00')

To Find Minimum number of rooms required run the below query:

create table #TempMeeting
(
 id int,Starttime time,EndTime time,MeetingRoomNo int,Rownumber int
)
insert into #TempMeeting select id, Starttime,EndTime,0 as MeetingRoomNo,ROW_NUMBER() 
over (order by starttime asc) as Rownumber from Meetings

declare @RowCounter int
select top 1 @RowCounter=Rownumber from #TempMeeting order by Rownumber

WHILE  @RowCounter<=(Select count(*) from #TempMeeting)
BEGIN
     update #TempMeeting set MeetingRoomNo=1
     where Rownumber=(select top 1 Rownumber from #TempMeeting where 
     Rownumber>@RowCounter and Starttime>=(select top 1 EndTime from #TempMeeting 
     where Rownumber=@RowCounter)and MeetingRoomNo=0)set @RowCounter=@RowCounter+1
END

select count(*) from #TempMeeting where MeetingRoomNo=0