Optimal room count and sizes for N overlapping Meeting Schedules

Question

I bumped into this question and I am not sure if my solution is optimal.

Problem

Given N weighted (Wi) and possibly overlapping intervals (representing meeting schedules) , find the minimum number "&" capacity of meeting rooms needed to conduct all meetings.

Example

|---10------|. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .|---------8---------|

        |------8-----|          |----------10-----------|

                  |--------6-------|

For the above schedule, we would need two meeting rooms of 10 and 10 capacitities. ( am i correct ? )

My Solution

Take a set of rooms, and traverse the intervals from the left, if we have a meeting room available with a capacity greater than needed use it, if there is none that meets the criteria, make a new room or increment the existing rooms with the new capacity.

Example:

Start of 10 - { 10 }

Start of 8 - { 10, 8 }

End of 10 - { 10-free, 8 }

Start of 6 - { 10, 8 }

End of 8 - {10, 8-free }

Start of 10 = { 10, 8+=2 } OR {10, 10 }

and so on.....

this is essentially greedy..

• Can someone prove this non-optimal?
• Whats the solution if this is non-optimal? DP ?

Answer 1

I believe that this problem is equivalent to "Minimum Number of Platforms Required for a Railway/Bus Station" problem.

This article http://www.geeksforgeeks.org/minimum-number-platforms-required-railwaybus-station/ explains well how to approach it.