title: Optimal room count and sizes for N overlapping Meeting Schedules
body: <p>I bumped into this question and I am not sure if my solution is optimal. </p>
  
  <h2>Problem</h2>
  
  <p>Given N weighted (Wi) and possibly overlapping intervals (representing meeting schedules) , find the minimum number "&amp;" capacity of meeting rooms needed to conduct all meetings.</p>
  
  <h2>Example</h2>
  
  <pre><code>|---10------|. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .|---------8---------|
  
          |------8-----|          |----------10-----------|
  
                    |--------6-------|
  </code></pre>
  
  <p>For the above schedule, we would need two meeting rooms of 10 and 10 capacitities. ( am i correct ? )</p>
  
  <h2>My Solution</h2>
  
  <p>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.</p>
  
  <p>Example: </p>
  
  <p>Start of 10 - { 10 }</p>
  
  <p>Start of 8 - { 10, 8 }</p>
  
  <p>End of 10 - { 10-free, 8 }</p>
  
  <p>Start of 6 - { 10, 8 }</p>
  
  <p>End of 8 - {10, 8-free }</p>
  
  <p>Start of 10 = { 10, 8+=2 } OR {10, 10 }</p>
  
  <p>and so on.....</p>
  
  <p>this is essentially greedy..</p>
  
  <ul>
  <li>Can someone prove this non-optimal?</li>
  <li>Whats the solution if this is non-optimal? DP ?</li>
  </ul>