title: (Dynamic programming) How to maximize room utilization with a list of meeting?
body: <p>I am trying this problem using dynamic programming</p>
  
  <h2>Problem:</h2>
  
  <p>Given a meeting room and a list of intervals (represent the meeting), for e.g.: </p>
  
  <ul>
  <li>interval 1: 1.00-2.00</li>
  <li>interval 2: 2.00-4.00</li>
  <li>interval 3: 14.00-16.00
  ...
  etc.  </li>
  </ul>
  
  <h2>Question:</h2>
  
  <p>How to schedule the meeting to maximize the room utilization, and <strong>NO meeting should overlap with each other</strong>?</p>
  
  <h2>Attempted solution</h2>
  
  <p>Below is my initial attempt in C# (knowing it is a modified Knapsack problem with constraints). However I had difficulty in getting the result correctly.</p>
  
  <pre><code>bool ContainsOverlapped(List&lt;Interval&gt; list)
      {
          var sortedList = list.OrderBy(x =&gt; x.Start).ToList();
          for (int i = 0; i &lt; sortedList.Count; i++)
          {
              for (int j = i + 1; j &lt; sortedList.Count; j++)
              {
                  if (sortedList[i].IsOverlap(sortedList[j]))
                      return true;
              }
          }
          return false;
      }
      public bool Optimize(List&lt;Interval&gt; intervals, int limit, List&lt;Interval&gt; itemSoFar){
          if (intervals == null || intervals.Count == 0)
              return true; //no more choice
  
          if (Sum(itemSoFar) &gt; limit) //over limit
              return false;
  
          var arrInterval = intervals.ToArray();
  
          //try all choices
          for (int i = 0; i &lt; arrInterval.Length; i++){
              List&lt;Interval&gt; remaining = new List&lt;Interval&gt;();
              for (int j = i + 1; j &lt; arrInterval.Length; j++) { 
                  remaining.Add(arrInterval[j]);
              }
  
              var partialChoice = new List&lt;Interval&gt;();
              partialChoice.AddRange(itemSoFar);
              partialChoice.Add(arrInterval[i]);
  
              //should not schedule overlap
              if (ContainsOverlapped(partialChoice))
                  partialChoice.Remove(arrInterval[i]);
  
              if (Optimize(remaining, limit, partialChoice))
                  return true;
              else
                  partialChoice.Remove(arrInterval[i]); //undo
          }
  
          //try all solution
          return false;
      }
  
  
  public class Interval
  {
      public bool IsOverlap(Interval other)
      {
          return (other.Start &lt; this.Start &amp;&amp; this.Start &lt; other.End) || //other &lt; this
                  (this.Start &lt; other.Start &amp;&amp; other.End &lt; this.End) || // this covers other
                  (other.Start &lt; this.Start &amp;&amp; this.End &lt; other.End) || // other covers this
                  (this.Start &lt; other.Start &amp;&amp; other.Start &lt; this.End); //this &lt; other
      }
      public override bool Equals(object obj){
          var i = (Interval)obj;
          return base.Equals(obj) &amp;&amp; i.Start == this.Start &amp;&amp; i.End == this.End;
      }
      public int Start { get; set; }
      public int End { get; set; }
      public Interval(int start, int end){
          Start = start;
          End = end;
      }
      public int Duration{
          get{
              return End - Start;
          }
      }
  }
  </code></pre>
  
  <h2>Edit 1</h2>
  
  <p><strong>Room utilization</strong> = amount of time the room is occupied. Sorry for confusion.</p>
  
  <h2>Edit 2</h2>
  
  <p>for simplicity: the duration of each interval is integer, and the start/end time start at whole hour (1,2,3..24)</p>