title: Appointment scheduling algorithm
body: <p>Suppose you need to schedule meetings for a CEO.  There must be as many meetings (count, not duration) scheduled as possible.</p>
  
  <p>The workday has a start time and end time.</p>
  
  <p>There are certain blocks of time unavailable (lunch, etc.)</p>
  
  <p>The input is a list of times.  The durations are either 30, 60, or 90 mins.</p>
  
  <p><strong>My approach</strong></p>
  
  <p>Represent the day as a boolean array.  The index is the time. Each array index represents 30 minutes.  So day[0] represents 9am and day[1] represents 9:30am.  day[1] = true means 9:30 is open and closed if false.</p>
  
  <p>Have a counter variable to keep track of the current earliest free time.  For each time, iterate through the list of meetings and see if current free time + meeting duration is open.  Runtime is O(N*N).</p>
  
  <p><strong>Flaw</strong></p>
  
  <p>However, my method does not result in the highest possible number of meetings squeezed into a day.  For example, I have a 120 minute free block, and potential meetings of 90, 60, and 60 minutes.  My algorithm first iterates to the 90 minute meeting and schedules it, but there is a 30 minute free block wasted.  Better would be to fit both 60 minute meetings in there instead.</p>
  
  <p><strong>Another idea</strong></p>
  
  <p>Get all combinations of potential meetings with a total duration of no more than 90 minutes, and keep track of the the maximum number of meetings.  I believe this would have to be done via permutation and O(N*N!) for each free block.  So the total runtime of this is O(N * N * N!).</p>
  
  <p>I would appreciate any feedback and alternative solutions.  Thanks!</p>